Aula ao vivo 01_22_02_21

Prévia do material em texto

Aspectos Teóricos da Computação
Aula ao vivo 
Prof. Hugo Insua
Aspectos Teóricos da Computação
Aula ao vivo 01
Alta Complexidade
Baixa Complexidade
Revisão da Hierarquia de Chomsky
Aspectos Teóricos da Computação
Aula ao vivo 01
Revisão da Hierarquia de Chomsky - Linguagem Regular
A análise de cada palavra de um programa escrito em uma Linguagem de Programação qualquer, denominada Análise Léxica, usa os algoritmos obtidos do estudo das Linguagens Regulares. Estes algoritmos são a realização do modelo computacional denominado Máquina de Estados Finitos.
Considere-se o alfabeto A = {a, b, c}. A partir deste alfabeto, podem ser definidas diferentes Linguagens.
Exemplos:
 LR = {w | w = an bb cm, n > 0, m >0}.
 
Trata-se de uma Linguagem Regular, pois não existe um vínculo entre o número de ocorrência dos diferentes símbolos “a”, “b” e “c”
Aspectos Teóricos da Computação
Aula ao vivo 01
Revisão da Hierarquia de Chomsky - Linguagem Livre de Contexto
A análise de cada comando (if, while, atribuição) e demais estruturas sintáticas (classes,declarações de variáveis, etc.) de um programa desenvolvido em uma Linguagem de Programação, a Análise Sintática, emprega algoritmos advindos de estudo das Linguagens Livres de Contexto.
Considere-se o alfabeto A = {a, b, c}. A partir deste alfabeto, podem ser definidas diferentes Linguagens.
 LL = {w | w = an bb cn, n > 0, n >0}.
 Trata-se de uma Linguagem Livre de Contexto, pois o número de ocorrências do símbolo “c” deve ser igual ao do símbolo “a”. Ao se verificar se uma palavra pertence a LL, um reconhecedor deveria ao identificar cada símbolo “c”, “lembrar-se”, que anteriormente foi encontrado um símbolo “a” correspondente. Sabe-se que para isto, uma memória organizada em pilha resolve conceitualmente o problema.
Aspectos Teóricos da Computação
Aula ao vivo 01
Revisão da Hierarquia de Chomsky - Linguagem Sensível a Contexto
Computacionalmente, uma linguagem sensível ao contexto é equivalente a uma máquina de Turing não determinística linearmente limitada, também chamado de autômato linearmente limitado. Ela é uma máquina de Turing não determinística com uma fita de apenas kn 'células', onde 'n' é o tamanho da entrada e 'k' é uma constante associada com a máquina. Isto significa que toda linguagem formal que pode ser decidida por uma máquina desse tipo é uma linguagem sensível ao contexto, e cada linguagem sensível ao contexto pode ser decidida por uma máquina desse tipo.
Considere-se o alfabeto A = {a, b, c}. A partir deste alfabeto, podem ser definidas diferentes Linguagens.
 Ld = {w | w = an (bb) n cn, n > 0, n >0}.
 Trata-se de uma Linguagem Dependente de Contexto.” Ao se verificar se uma palavra pertence a LD, um reconhecedor deveria memorizar não somente cada ocorrência do símbolo “a”, como também cada ocorrência da cadeia “bb” para poder, finalmente, aceitar cada ocorrência do símbolo “c”. Pode-se constatar que, conceitualmente, para se resolver este problema seriam necessárias duas pilhas.
Aspectos Teóricos da Computação
Aula ao vivo 01
Definição formal Máquina de Turing: Linguagens Recursivas e Recursivamente Enumeráveis
As máquinas de Turing são similares aos autômatos finitos e de pilha e
apresentam fita de entrada e unidade de controle finito. A figura abaixo ilustra a estrutura de uma Máquina de Turing.
Note-se que a fita de entrada não é finita e sim, ilimitada à direita. Por outro
lado, o seu início é marcado pelo símbolo especial “•”. Cumpre observar, que há autores que apresentam a máquina de Turing como ilimitada à direita e à esquerda. Sobre a fita de entrada podem ser executadas as operações de leitura e escrita. Ainda, o cursor pode movimentar-se à direita e à esquerda. O símbolo gravado e o sentido do movimento são definidos pelo programa da unidade de controle. 
Aspectos Teóricos da Computação
Aula ao vivo 01
Definição formal Máquina de Turing: Linguagens Recursivas e Recursivamente Enumeráveis
O programa é uma função tal que dependendo do estado corrente da máquina e do símbolo lido, são determinados: o próximo estado, o sentido do movimento do cursor e o símbolo a ser gravado na fita.
Como a fita é ilimitada à direita, inicialmente, a palavra a ser processada ocupa as células mais à esquerda, sendo que as demais células são aqui denotadas por , ou seja, células em branco.
Aspectos Teóricos da Computação
Aula ao vivo 01
Definição formal Máquina de Turing: Linguagens Recursivas e Recursivamente Enumeráveis
Uma MT é constituída de:
a)Uma fita, infinita para a direita, dividida em células 
Cada célula está em branco ou contém algum símbolo de um alfabeto = {s0, s1,...,sn}
b) Um cabeçote de leitura
Aspectos Teóricos da Computação
Aula ao vivo 01
Definição formal Máquina de Turing: Linguagens Recursivas e Recursivamente Enumeráveis
b) Um cabeçote de leitura
Aspectos Teóricos da Computação
Aula ao vivo 01
Definição formal Máquina de Turing: Linguagens Recursivas e Recursivamente Enumeráveis
c) Um registrador de estados Q= {q0, q1, q2, ..., qm} cabeçote de leitura
Aspectos Teóricos da Computação
Aula ao vivo 01
Definição formal Máquina de Turing: Linguagens Recursivas e Recursivamente Enumeráveis
d) Um conjunto de instruções I 
Cada instrução é uma quádrupla da forma (qi, sj, , ql)
Como uma MT interpreta uma instrução?
Aspectos Teóricos da Computação
Aula ao vivo 01
Definição formal Máquina de Turing: Linguagens Recursivas e Recursivamente Enumeráveis
Uma instrução da forma (qi, sj, , ql), informa à MT que, estando ela no estado qi, lendo o símbolo sj, faça o seguinte;
Se 𝛼 = sk, apague sj e escreva sk na célula que está sendo lida
Se 𝛼 = D, mova o cabeçote de leitura uma célula para a direita
Se 𝛼 = E, mova o cabeçote de leitura uma célula para a esquerda
Modifique o estado atual da máquina para ql
Aspectos Teóricos da Computação
Aula ao vivo 01
Definição formal Máquina de Turing: Linguagens Recursivas e Recursivamente Enumeráveis
Exemplo de Instrução
Consideremos uma MT com a seguinte configuração
i1 = (q1, 0, D, q1)
I2 = ( q1, 1, 0, q2)
Aspectos Teóricos da Computação
Aula ao vivo 01
Definição formal Máquina de Turing: Linguagens Recursivas e Recursivamente Enumeráveis
Exemplo de Instrução
Consideremos uma MT com a seguinte configuração
i1 = (q1, 0, D, q1)
I2 = ( q1, 1, 0, q2)
i1 = (q1, 0, D, q1)
Aspectos Teóricos da Computação
Aula ao vivo 01
i1 = (q1, 0, D, q1)
I2 = ( q1, 1, 0, q2)
i1 = (q1, 0, D, q1)
I2 = ( q1, 1, 0, q2)
Aspectos Teóricos da Computação
Aula ao vivo 01
Definição formal Máquina de Turing: Linguagens Recursivas e Recursivamente Enumeráveis
Máquina de Turing
É um quíntupla caracterizada por MT= (Q, , I, qi, F), onde:
Q = {q0, q1, q2, ..., qm} é o seu conjunto de estados
 = {s0, s1,...,sn} é o seu alfabeto
I = (qi, sj, , ql) é o seu conjunto de instruções
qi Q é o seu estado inicial
F Q é o seu conjunto de estados finais
Aspectos Teóricos da Computação
Aula ao vivo 01
Definição formal Máquina de Turing: Linguagens Recursivas e Recursivamente Enumeráveis
Exercício
Aspectos Teóricos da Computação
Aula ao vivo 01
Definição formal Máquina de Turing: Linguagens Recursivas e Recursivamente Enumeráveis
Exercício
Aspectos Teóricos da Computação
Aula ao vivo 01
Definição formal Máquina de Turing: Linguagens Recursivas e Recursivamente Enumeráveis
Exercício
Aspectos Teóricos da Computação
Aula ao vivo 01
Definição formal Máquina de Turing: Linguagens Recursivas e Recursivamente Enumeráveis
Exercício
Aspectos Teóricos da Computação
Aula ao vivo 01
Definição formal Máquina de Turing: Linguagens Recursivas e Recursivamente Enumeráveis
Exercício
Aspectos Teóricos da Computação
Aula ao vivo 01
Definição formal Máquina de Turing: Linguagens Recursivas e Recursivamente Enumeráveis
Exercício
Aspectos Teóricos da Computação
Aula ao vivo 01
Definição formal Máquina de Turing: Linguagens Recursivas e Recursivamente Enumeráveis
Exercício 1
AspectosTeóricos da Computação
Aula ao vivo 01
Definição formal Máquina de Turing: Linguagens Recursivas e Recursivamente Enumeráveis
Exercício 1
MT= (Q, , I, qi, F), onde:
Q = {q1, q2, q3} 
 = {0,1} 
I = {i1, i2, i3, i4} = { (q1 , 1, D, q1 ), ..., (q2, 0, D, q3 )}
qi = q1 
F = {q3}
Aspectos Teóricos da Computação
Aula ao vivo 01
Definição formal Máquina de Turing: Linguagens Recursivas e Recursivamente Enumeráveis
Exercício 2
Consideremos as seguintes configurações
Aspectos Teóricos da Computação
Aula ao vivo 01
Definição formal Máquina de Turing: Linguagens Recursivas e Recursivamente Enumeráveis
Exercício 2
Consideremos as seguintes configurações