MÓDULO 2 - DEFINIÇÃO FORMAL DE MÁQUINAS DE TURING; LINGUAGENS RECURSIVAS E RECURSIVAMENTE ENUMERÁVEIS

Prévia do material em texto

Módulo 2 – Máquinas de Turing – Parte I 
 
 Este módulo tem por objetivo apresentar: a definição formal da Mpaquina de 
Turing, bem como definir i conceito de linguagens recursivas e linguagens 
recursivamente enumeráveis. 
A figura 1 ilustra a máquina de Turing, dispositivo aceitador de Linguagens 
Irrestritas. Trata-se de um modelo conceitual que simula procedimentos 
computacionais mais gerais que os autômatos finitos e os autômatos de pilha.. 
Controle finito
1 2 ... b b> ...
Início da fita de 
entrada
cursor
Função de transição
entrada b: branco
 
Figura 1 – Máquina de Turing 
Pode-se afirmar a respeito da Máquina de Turing que: 
 O cursor de acesso à fita de entrada pode se deslocar livremente sobre a fita 
de trabalho. 
 Apresenta a fita de entrada ilimitada à direita. 
 Apresenta um conjunto finito de estados. 
 A Fita de entrada (dispositivo de armazenamento) é passível de ser lida e 
escrita. 
A seguir apresenta-se a definição formal da Máquina de Turing segundo duas 
clássicas referências bibliográficas. 
Definição formal da máquina de Turing (Ramos, José Neto e Vega) 
 Uma máquina de Turing é definida como M = (Q, A, , g, q0, >, b, F), onde> 
 Q é o conjunto finito não vazio de estados. 
 A é o alfabeto de entrada, formado por um conjunto não vazio de símbolos. 
 é o conjunto finito e não vazio de símbolos que podem ser lidos e/ou 
escritos na fita de trabalho.   A. 
 q0Q é o estado inicial. 
 F  Q é o conjunto de estados finais 
 “>“ , “>“ A, é o símbolo que indica a primeira posição da fita de entrada. Não 
pode ser gravado em nenhuma outra posição da fita. 
 b , b  A: preenche todas as posições à direita da cadeia de entrada da fita. 
 g é a função parcial de transição. 
 g: Q  2Q  {E,D} 
 “E”, “D” indicam o movimento do cursor para a esquerda e para a direita. 
 
Exemplo 1: Seja a máquina de Turing T, em que: 
Q = {q0, qf} 
A = {0, 1} 
 = {0, 1, #} 
F = {qf} 
 
Ainda, a função de transição g é tal que: 
g(q0, >) = (q0, >, D) 
g(q0, 0) = (q0,1, D) 
g(q0, 1) = (q0, 0, D) 
g(q0, b) = (qf ,#, E) 
 
Observe – se a figura 2, que simula o reconhecimento da cadeia “01”. 
> 0 1

q0
> 0 1

q0
> 1 1

q0
> 1 0

q0
> 1 0 #

qf
 
Figura 2 – Reconhecimento da cadeia “01” 
Exemplo 2: Seja a máquina de Turing MT, tal que: 
 Q = {q0, q1, q2, q3, qf} 
 A = {a,b} 
  = {a, b, A, B} 
 q0 é o estado inicial e qf é o estado final. 
 , representa espaço em branco. 
Ainda, tem-se que: 
g(q0, >) = (q0, >, D) g(q0, a) = (q1, A, D) 
g(q0, b) = (q3, B, D) g(q0, )= (qf, , D) 
g(q1, a) = (q1, a, D) g(q1, b) = (q2, B, E) 
g(q1, B)= (q1, B, D) g(q2, a) = (q2, a, E) 
g(q2, A) = (q0, A, D) g(q2, B)= (q2, B, E) 
g(q3, B) = (q3, B, D) g(q3, ) = (qf, , D) 
 
Esta Máquina reconhece a linguagem Livre de Contexto L = {a
n
 b
n
}. Sejam observadas as figura 
3a e 3b: 
 
a) 
> a a b b  ...
q0
> a a b b  ...
q0
> A a b b  ...
q1
> A a b b  ...
q1
> A a B b  ...
q2
> A a B b  ...
q2
 
b) 
> A A B B  ...
q2
> A A B B  ...
q0
A A B b  ...
q1
> A A B B  ...
q2
> A A B B  ...
q2
> A A B B  ...
q0
 
Figuras 3 (a e b) – Reconhecimento da cadeia “aabb” 
 
 
 Definição formal da máquina de Turing (Lewis, Papadimitrious) 
 Uma máquina de Turing é uma quíntupla (Q, A, , q0, F, g), onde: 
 Q é o conjunto de estados; 
 A é o alfabeto, contendo o símbolo de espaço em branco  e o símbolo 
de início de fita . Não contém os símbolos  e  (indicadores de movimento 
do cursor para a esquerda e para a direita, respectivamente.). 
 q0  Q é o estado inicial; 
 F  Q é o conjunto de estados de parada; 
 g é a função de transição, com : 
 g: (Q-F)  A  (Q  (A  { , }), tal que: 
a) para todo q  Q – F, se g(q,) = (p, b), então b =  
b) para todo q  Q – F, se a  A, se g(q, a) = (p, b) então b   
 
 
Linguagem Recursivamente Enumerável 
 Seja uma máquina de Turing M = (Q, A, , q0, F, g), seja A0  A – {, } um alfabeto e seja a 
linguagem L  A0*. 
 Observação: A0* significa o conjunto de todas as palavras que podem ser formuladas, a partir 
do alfabeto A, exceção feita aos símbolos  e . 
 
Diz-se que M semidecide L, se para qualquer palavra w  A0*: se e somente se M para quando 
a palavra w pertencer a L. 
Uma Linguagem L é recursivamente enumerável se e somente se existe uma máquina de 
Turing que semidecide L. 
Note-se que a definição acima deixa em aberto dois comportamentos possíveis para a 
máquina M ao se verificar se uma palavra não estiver em L, a saber: 
 M pode parar em um estado que não seja de “parada” ou... 
 M pode não parar. 
 
Linguagem Recursiva 
Considere uma Máquina de Turing M = (Q, A, g, q0, F), onde F = {sim, não} 
Uma configuração de aceitação é aquela cujo estado final é sim. 
Uma configuração de rejeição é aquela cujo estado final é não. 
Seja A0  A – {, } 
Diz-se que uma máquina de Turing M aceita uma palavra w  L  A0* se o seu 
processamento resulta em uma configuração de aceitação. Por outro lado, diz-se que M 
rejeita w se o processamento resulta em uma configuração de rejeição. 
Diz-se que M decide uma Linguagem L  A0*, se M aceita a cadeia w  L e M 
rejeita toda cadeia w L. 
Uma Linguagem é recursiva se existe uma máquina de Turing que a decide. 
Teorema: Se uma Linguagem é recursiva, então também é recursivamente enumerável. 
 
Exercício Resolvido 1: Considere a Máquina de Turing M = (Q, A, g, q0, F), 
onde: 
Q = {q0, q1, q2, q3} 
A = {0, , , I, P } 
F = {q3 } 
Ainda: 
g(q0, ) = (q0, ) 
g(q0, 0) = (q1, ) 
g(q1, 0) = (q2, ) 
g(q1, ) = (q3, I) 
g(q2, 0) = (q1, ) 
g(q2, ) = (q3, P) 
 
Considere ainda, a seguinte fita de entrada: 
 0 0 0        … 
 
q0 
 
Pede-se a configuração final da fita de entrada, após o reconhecimento da 
cadeia de entrada. 
Tem-se a seguinte sequência do reconhecimento: 
 
 0 0 0        … 
 
q0 
 
 0 0 0        … 
  
 q0 
 
 0 0 0        … 
  
 q1 
 
 0 0 0        … 
  
 q2 
 
 0 0 0        … 
  
 q1 
 
 0 0 0 I       … 
  
 q3 
 
Exercício Resolvido 2: Considere a Máquina de Turing M = (Q, A, g, q0, F), 
onde: 
Q = {q0, q1, q2, q3, q4} 
A = {0, 1, , , I, P } 
F = {q4 } 
Ainda: 
g(q0, ) = (q0, ) 
g(q0, 0) = (q1, ) 
g(q1, 0) = (q2, ) 
g(q1, ) = (q3, I) 
g(q2, 0) = (q1, ) 
g(q2, ) = (q3, P) 
g(q3, P) = (q3, ) 
g(q3, I) = (q3, ) 
g(q3, 0) = (q3, 1) 
g(q3, 1) = (q3, ) 
g(q3, ) = (q4, ) 
 
 
Considere ainda, a seguinte fita de entrada: 
 0 0 0        … 
 
q0 
 
Pede-se a configuração final da fita de entrada, após o reconhecimento da 
cadeia de entrada. 
Tem-se a seguinte sequência do reconhecimento: 
 0 0 0        … 
 
q0 
 
 0 0 0        … 
  
 q0 
 
 0 0 0        … 
  
 q1 
 
 0 0 0        … 
  
 q2 
 
 0 0 0        … 
  
 q1 
 
 0 0 0 I       … 
  
 q3 
 0 0 0 I       … 
  
 q3 
 
 0 0 1 I       … 
  
 q3 
 
 0 0 1 I       … 
  
 q3 
 0 1 1 I       … 
  
 q3 
 0 1 1 I       … 
  
 q3 
 
 
 1 1 1 I       … 
  
 q3 
 
 1 1 1 I       … 
 
q3 
 
 1 1 1 I       … 
  
 q4 
 
 
 
 
 
 
 
 
 
 
 
 
Referências: 
 
Cormen T. H., Leiserson C. E. ; Rivest, C. S. Algoritmos Campus, 2012. 
Lewis H. R. ; Papadimitrious, C. H. Elementos da Teoria da Computação 
RAMOS, Marcus ViniciusMidena. NETO; João José. VEGA, Italo Santiago. 
Linguagens Formais. Teoria, Modelagem e Implementação Porto Alegre: Bookman, 
2009. 
 MENEZES, Paulo Blauth. Linguagens formais e autômatos. Porto Alegre: Bookman, 
2008.