Máquina de Turing - Parte II

Prévia do material em texto

DIAGRAMAS DE TRANSIÇÃO PARA 
MÁQUINAS DE TURING 
Marcelo Guerra 
INTRODUÇÃO 
 É possível representar as transições de uma MT 
através de diagramas. 
 
 Um diagrama de transição consiste em: 
 
 Um conjunto de nós correspondendo aos estados da MT. 
 Um arco do estado q para o estado p é rotulado por um 
ou mais itens da forma X/YD. 
 X e Y são símbolos da fita. 
 D é o sentido do movimento da cabeça da fita. 
INTRODUÇÃO 
 Assim, para δ(q, X) = (p, Y, D) 
 Temos um arco rotulado X/Y D de q para p. 
 
 Nos diagramas, o sentido é indicado por ← 
“esquerda” ou → “direita”. 
 
 O estado inicial e os estados finais são 
representados da maneira usual. 
 
 O símbolo branco da fita é representado por B. 
EXEMPLO 
q0 q1 q2 
 
Y / Y → 
0/0 → 
 
q4 
 
q3 
Y / Y → 
 
B / B → 
 
0 / X → 
 
Y / Y ← 
0 / 0 ← 
Y / Y → 
 
 
X / X → 
 
1 / Y ← 
Estado 0 1 X Y B 
q0 (q1,X,R) (q3,Y,R) 
q1 (q1,0,R) (q2,Y,L) (q1,Y,R) 
q2 (q2,0,L) (q0,X,R) (q2,Y,L) 
q3 (q3,Y,R) (q4,B,R) 
q4 
MÁQUINAS DE TURING COMO TRADUTORES 
(COMPUTADORES) 
 As máquinas de Turing não são somente 
interessantes como reconhecedores. 
 
 Elas nos fornecem modelos abstratos de 
computadores digitais. 
 
 Uma vez que o principal objetivo de um 
computador é transformar entradas em saídas, 
ele atua como um tradutor. 
MÁQUINAS DE TURING COMO TRADUTORES 
(COMPUTADORES) 
 A entrada para uma computação é a cadeia 
disposta na fita no início da computação. 
 
 Na conclusão da computação, a saída será a 
cadeia que se encontrar na fita. 
 
 Se a máquina pára num estado não final ou fica 
em laço infinito para uma entrada, dizemos que a 
MT não está definida para essa entrada. 
MÁQUINAS DE TURING COMO TRADUTORES 
(COMPUTADORES) 
 Para computar funções numéricas, há a 
necessidade de codificação dos números naturais 
na fita da máquina. 
 
 Uma possibilidade é codificá-los na notação 
unária, na qual qualquer inteiro positivo é 
representado por: 
 
 Ex: 1 é 1, 2 é 11, 3 é 111, ... 
    1x
EXEMPLO 
 Dados dois inteiros positivos x e y, projetar uma 
máquina de Turing que compute x + y. 
 
 Inicialmente, x e y são dispostos na fita e sua soma 
deve aparecer no final da computação. 
 
 α(x) e α(y) estão na fita em notação unária, separados 
por um 0. 
 
 O cabeçote aponta para o símbolo mais à esquerda de 
α(x). 
 
 q0α(x)0α(y) ⊦ qf α(x+y)0 
EXEMPLO 
 Tudo o que precisamos fazer é mover o separador 
0 para a direita, até o final de α(y). 
 
 Deste modo, a adição nada mais é do que 
concatenar as duas cadeias. 
 
 Ex: 2 + 3 => 11 + 111 => 11111 
EXEMPLO 
 M = {Q, Σ, Γ, δ, q0, B, F}, 
 
 Com: 
 Q = {q0, q1, q2, q3, q4} 
 Σ = {0 ,1} 
 Γ = {0,1,B} 
 F = {q4} 
0 1 B 
q0 (q1, 1, D) (q0, 1, D) 
q1 (q1, 1, D) (q2, B, E) 
q2 (q3, 0, E) 
q3 (q3, 1, E) (q4, B, D) 
q4 
EXEMPLO 
 Somar 111 com 11: 
 
 q0111011 ⊦ 1q011011 ⊦ 11q01011 ⊦ 111q0011 
⊦ 1111q111 ⊦ 11111q11 ⊦ 111111q1B ⊦ 11111q21 
⊦ 1111q310 ⊦ 111q3110 ⊦ 11q31110 ⊦ 1q311110 
⊦ Bq3111110 ⊦ Bq3B111110 ⊦ Bq4111110 
A LINGUAGEM DE UMA MT 
 Uma MT aceita uma linguagem da seguinte 
forma: 
 
 Uma string de entrada é colocada na fita. 
 
 A cabeça aponta para o símbolo mais à esquerda. 
 
 Se a MT entrar em um estado de aceitação, a entrada 
será aceita. Caso contrário, será rejeitada. 
PARADA PARA MT’S 
 Uma segunda noção de “aceitação” para MT’s é a 
aceitação por parada. 
 
 Dizemos que uma MT pára se ela entra em um 
estado q, varrendo um símbolo da fita X e não 
existe mais nenhum movimento nessa situação. 
 Ou seja, δ(q, X) está indefinido 
 
 Algumas máquinas não são projetadas para 
reconhecer uma linguagem, e sim, calcular 
funções. Nesse caso, não há a necessidade de um 
estado de aceitação 
 
 
PARADA PARA MT’S 
 Sempre podemos supor que uma MT irá parar se 
ela aceitar a string de entrada. 
 Ou seja, sem alterar a linguagem podemos tornar 
δ(q, X) indefinido sempre que q for um estado de 
aceitação. 
 
 
 Em geral dizemos que: 
 
 Uma MT sempre pára quando se encontra em 
um estado de aceitação. 
A LINGUAGEM DE UMA MT 
 Seja M = (Q, Σ, Γ, δ, q0, B, F) uma MT. 
 
 L(M) é o conjunto de strings w em Σ* tais que 
 q0w ⊦
* αpβ para algum estado p em F e quaisquer strings de 
fita α e β. 
 
 O conjunto de linguagens que podem ser aceitas por 
MT’s é chamado de Linguagens Recursivamente 
Enumeráveis. 
 
 Segundo a Hipótese de Church, a MT é o mais geral 
dispositivo de computação. 
 
 Então, as linguagens recursivamente enumeráveis 
representam todas as linguagens que podem ser 
reconhecidas mecanicamente e em tempo finito. 
 
A LINGUAGEM DE UMA MT 
 Linguagens Recursivamente Enumeráveis 
 Formalismo: Gramática Irrestrita. 
 
 Para algumas dessas linguagens, é impossível 
determinar mecanicamente se uma palavra não 
pertence a L. 
 Existe pelo menos um w não pertencente a L, que ao 
ser processada por MT, a máquina entra em loop 
infinito. 
 
 A classe das linguagens para as quais existe pelo 
menos uma MT que pára para qualquer entrada, 
aceitando-a ou rejeitando-a chama-se Linguagens 
Recursivas. 
A LINGUAGEM DE UMA MT 
 As linguagens sensíveis ao contexto são aquelas 
que podem ser aceitas por uma máquina de 
Turing com fita limitada. 
 Formalismo: Gramática Sensível ao contexto. 
 
 A classe das linguagens sensíveis ao contexto 
está contida na classe das linguagens recursivas. 
HIERARQUIA DAS LINGUAGENS 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Linguagens Recursivamente Enumeráveis 
 
 
 
 
 
 
 
 
 
 
 
Linguagens Recursivas 
 
 
 
 
 
 
 
Linguagens Sensíveis ao contexto 
 
 
 
 
 
Linguagens Livres de Contexto 
Linguagens 
Regulares 
EXERCÍCIO 
 A MT permite calcular qual função matemática? 
 
 
 
 
 
 
 
 
 Resp: f(n)=n+1 
EXERCÍCIO 
 Dada a MT abaixo, verifique se as sentenças a 
seguir são aceitas ou não: 
 aabbcc 
 abbacc 
 
 
 
 
 
 
 
 Resposta: sim e não 
EXERCÍCIO 
 Qual linguagem é representada pela MT abaixo? 
 
 
 
 
 
 
 
 
 
 
 
 anbncn para n>=0