Máquina de Turing

Prévia do material em texto

UERJ Universidade do Estado do Rio de Janeiro
IME Instituto de Matemática e Estatística
DICC Departamento de Informática e Ciência da Computação - Profa. Maria Alice Silveira de Brito
Teoria da Computação Lista 2
4. Utilizando a mT M4, M4 = ( K, , , ,i , F), em que K = { q0, q1, q2, q3, q4 },  = {a, b},  = {a, b, X, Y,  }, i = q0, F = { q4 } e 
	
	a
	b
	X
	Y
	
	q0
	q1XR
	
	
	q3YR
	q4XR
	q1
	q1aR
	q2YL
	
	q1YR
	
	q2
	q2aL
	
	q0XR
	q2YL
	
	q3
	
	
	
	q3YR
	q4XR
	q4
	
	
	
	
	
Verifique se as cadeias aab e abbaa são aceitas por esta mT M4, mostrando a sequência de configurações assumidas por M6 ao tentar reconhecer cada cadeia.
Neste caso basta seguir a tabela:
Vc vai ler a palavra aab, então posicione o q0 antes da palavra:
q0aab ( pela tabela quando q0 encontra a ele vira q1 escreve X e anda para a direita. Vou marcar as alterações de vermelho p n ter q escrever passo-a-passo, é só comparar com a tabela:
q0aab ( Xq1ab ( Xaq1b ( Xq2aY ( q2XaY ( Xq0aY ( XXq1Y ( XXYq1 ( A máquina para pq n existe previsto o que acontece quando ela q1 lê a palavra vazia, por isso não se chega ao estado final q4, portanto a cadeia aab não é aceita por essa máquina.
5.ª) Construa uma mT M5 que reconheça as cadeias da linguagem L5 = { anbncn  n  1 }.
Essa linguagem aceita a palavra aabbcc, segundo sua regra. Então, partindo deste exemplo, montamos a máquina. O macete é preencher as letras que se repetem depois de preencher pelo menos uma de cada. Ou seja, a cabeça da máquina vai até o final e volta até preencher tudo.
Como no anterior, deve-se colocar o estado inicial q0 antes da palavra e decidir o que ele faz qdo lê cada letra, isso pode ser feito como rascunho pq nessa questão ele só cobra a tabela, a n ser q peça um exemplo. Assim:
q0aabbcc ( Xq1abbcc ( Xaq1bbcc ( XaYq2bcc ( XaYbq2cc ( XaYq3bZc ( Xaq3YbZc ( Xq3aYbZc ( q3XaYbZc ( Xq0aYbZc ( XXq1YbZc ( XXYq1bZc ( XXYYq2Zc ( XXYYZq2c ( XXYYq3ZZ ( XXYq3YZZ ( XXq3YYZZ ( Xq3XYYZZ ( XXq0YYZZ ( XXYq0YZZ ( XXYYq0ZZ ( XXYYZq0Z ( XXYYZZq0 ( XXYYZq4Z
Depois disso vc vai jogando na tabela o q vc fez em cada passo ou monta como na pilha:
Como pilha:
δ(q0,a)=(X,q1,R)
δ(q1,a)=(a,q1,R)
δ(q1,b)=(Y,q2,R)
δ(q2,b)=(b,q2,R) Até aqui ele vai transformando as primeiras letras de cada
δ(q2,c)=(Z,q3,L) A partir daqui ele volta até achar a primeira letra transformada
δ(q3,b)=(b,q3,L)
δ(q3,Y)=(Y,q3,L)
δ(q3,a)=(a,q3,L)
δ(q3,X)=(X,q0,R) Agora ele vai começar a transformar a segunda letra e fica no loop até transformar todas. Agora tem q ver o q acontece qdo q0 lê o Y e o Z pq todas as letras já terão sido transformadas.
δ(q0,Y)=(Y,q0,R)
δ(q0,Z)=(Z,q0,R) Quando a cabeça (ponteiro ou estado) chega ao final da sequencia ela lê a palavra vazia. É o momento de chegar ao estado final. Como não dá mais para andar p direita, anda-se uma posição para a esquerda.
δ(q0,ε)=(Z,q4,L)
Na tabela
	δ
	a
	b
	c
	X
	Y
	Z
	ε
	q0
	X,q1,R
	
	
	
	Y,q0,R
	Z,q0,R
	Z,q4,L
	q1
	a,q1,R
	Y,q2,R
	
	
	
	
	
	q2
	
	b,q2,R
	Z,q3,L
	
	
	
	
	q3
	a,q3,L
	b,q3,L
	
	X,q0,R
	Y,q3,L
	
	
Obs.: ε pode ser diamante Tb
pag.� PAGE �1� -� DATE \@"DD\/MM\/YY" �07/03/13�