exercicios maquina de turing

Prévia do material em texto

Lista de Exercícios
Nome: Data:
1 Máquinas de Turing
Considerando a máquina de Turing abaixo.
q0
início q1 q2 q4
(}, }, D)
(0, 0, D)
(0, 0, D)(1, 1, D)
1.1 Descreva qual a linguagem aceita pela máquina de Turing ilustrada acima.
1.2 É possível que a cabeça de leitura/gravação de uma máquina de Turing fique na mesma célula e leia o valor
de tal célula duas vezes consecutivas? Se sim, explique em qual cenário isso é possível.
1.3 É possível que uma máquina de Turing possua somente um estado? Justifique sua resposta.
1.4 Construa uma máquina de Turing que reconheça a seguinte linguagem: L1 = {w ∈ {0, 1}∗ | w possui pelo
menos dois símbolos iguais, sendo que um deles aparece no final de w}. Desenhe o diagrama de tal máquina.
Lista de Exercícios
1.5 Descreva como a máquina de Turing que aceita L1 processa as palavras 11 e 01011. Ilustre as configurações
da máquina durante o processamento.
1.6 Construa uma máquina de Turing que reconheça a seguinte linguagem: L2 = {w♥wR | w ∈ {0, 1}∗ e wR é a
palavra w inversa}. Desenhe o diagrama de tal máquina.
1.7 Descreva como a máquina de Turing que aceita L2 processa as palavras 101♥101 e 10♥01. Ilustre as
configurações da máquina durante o processamento.
	Máquinas de Turing
	 Descreva qual a linguagem aceita pela máquina de Turing ilustrada acima. 
	É possível que a cabeça de leitura/gravação de uma máquina de Turing fique na mesma célula e leia o valor de tal célula duas vezes consecutivas? Se sim, explique em qual cenário isso é possível.
	É possível que uma máquina de Turing possua somente um estado? Justifique sua resposta.
	Construa uma máquina de Turing que reconheça a seguinte linguagem: L1 = {w {0, 1}* | w possui pelo menos dois símbolos iguais, sendo que um deles aparece no final de w}. Desenhe o diagrama de tal máquina.
	Descreva como a máquina de Turing que aceita L1 processa as palavras 11 e 01011. Ilustre as configurações da máquina durante o processamento.
	Construa uma máquina de Turing que reconheça a seguinte linguagem: L2 = {wwR | w {0, 1}* e wR é a palavra w inversa}. Desenhe o diagrama de tal máquina.
	Descreva como a máquina de Turing que aceita L2 processa as palavras 101101 e 1001. Ilustre as configurações da máquina durante o processamento.