Exercícios Maquina de Turing

Prévia do material em texto

MINISTÉRIO DE EDUCAÇÃO
UNIVERSIDADE FEDERAL RURAL DO RIO DE JANEIRO
Instituto Multidisciplinar
Departamento de Ciência da Computação
Curso de Ciência da Computação
Linguagens Formais e Autômatos
Lista de Exercícios No. 05
Máquina de Turing
1) Qual a importância da Máquina de Turing para a Ciência da Computação?
2) Para cada uma das linguagens abaixo, desenvolva uma Máquina de Turing que a aceita e que, sempre
para, para qualquer entrada:
a) Ø
b) {ɛ} 
c) {ɛ, a, b} 
d) {a, b}* 
e) {anbncn | n  0} 
f) {w | w é palavra de {x, y, (, )}* com parênteses balanceados}
g) {w  {a,b}* | w tenha pelo menos um “a”}
h) {w  {a, b}* | o décimo símbolo da direita para a esquerda de w é a}
i) {w  {0,1}* | w contém duas vezes mais 0's que 1's}
j) {anbnan | n  1}
k) {cwc | w {0,1}*}
l) {wcwR | w  {a,b}*}
3) Sobre a Hipótese de Church:
a) Por que não é demonstrável?
b) Qual o seu significado?
c) Qual a sua importância?
4) Examine a definição formal de uma Máquina de Turing e responda as seguintes questões.
a) Uma MT pode alguma vez escrever o símbolo branco em sua fita? 
b) O alfabeto de fita pode ser o mesmo que o alfabeto de entrada?
c) Uma MT pode conter apenas um estado?
5) Projete Máquinas de Turing que façam as seguintes operações:
a) Verificar se um número binário é par. Se sim, retorna 1, senão, retorna 0. Ex: Sendo “110” o input, saída:
110$0.
b) Verificar quantas letras uma string possuiu na base unária. Ex: Sendo “aaba” o input, saída: aaba$1111.
c) Verificar quantas letras a's e b's possuem uma string anbm na base unária. Ex: Sendo “aabbb” o input, saída:
aabbb$11$111.
6) (POSCOMP 2008) Assinale a afirmativa INCORRETA:
(a) Existe uma máquina de Turing U que simula qualquer outra máquina de Turing M sobre qualquer entrada
para M.
(b) A Tese de Church afirma que o conceito informal de procedimento efetivo é capturado pelo conceito
formal de Máquina de Turing.
(c) Uma linguagem é recursivamente enumerável se, e somente se, for aceita por alguma Máquina de Turing.
(d) Existe uma máquina de Turing T que, dada qualquer máquina de Turing M e qualquer entrada w para M,
T determina, em um número finito de passos, se M pára para a entrada w ou não.
(e) Toda linguagem recursiva é recursivamente enumerável, mas o inverso nem sempre é verdadeiro.
7) (ENADE 2005)
Estado Símbolo lido na
fita
Símbolo gravado
na fita
Direção Próximo estado
Início • • Direita 0
0 0 1 Direita 0
0 1 0 Direita 0
0 B B Esquerda 1
1 0 0 Esquerda 1
1 1 1 Esquerda 1
1 • • Direita Parada
Na tabela acima, estão descritas as ações correspondentes a cada um dos quatro estados (início, 0, 1, parada)
de uma máquina de Turing, que começa a operar no estado “início” processando símbolos do alfabeto {0,1,•,
B}, em que ‘B’ representa o espaço em branco. Considere que, no estado “início”, a fita a ser processada
esteja com a cabeça de leitura/gravação na posição 1, conforme ilustrado a seguir.
 
1 2 3 4 5 6 7 8 9 10 11 ...
• 0 1 1 0 1 B B B B B ...
Considerando essa situação, assinale a opção que indica corretamente a posição da cabeça de leitura/gravação
e o conteúdo da fita após o término da operação, ou seja, após a máquina atingir o estado “parada”:
(a) 
1 2 3 4 5 6 7 8 9 10 11 ...
• 0 0 1 1 1 1 0 0 1 1 ...
(b)
1 2 3 4 5 6 7 8 9 10 11 ...
• 0 1 1 0 1 B B B B B ...
(c)
1 2 3 4 5 6 7 8 9 10 11 ...
• 0 1 1 0 1 0 1 0 0 1 ...
(d)
1 2 3 4 5 6 7 8 9 10 11 ...
• B B B B B 1 B B B B ...
(e)
1 2 3 4 5 6 7 8 9 10 11 ...
• 1 0 0 1 0 B B B B B ...
8) (Exercício complementar) (ENADE 2011) O problema da parada para máquinas de Turing, ou
simplesmente problema da parada, pode ser assim descrito: determinar, para quaisquer máquinas de Turing
M e palavra w, se M irá eventualmente parar com entrada w. Mais informalmente, o mesmo problema
também pode ser assim descrito: dados um algoritmo e uma entrada finita, decidir se o algoritmo termina ou
se executará indefinidamente. Para o problema da parada, 
(a) existe algoritmo exato de tempo de execução polinomial para solucioná-lo. 
(b) existe algoritmo exato de tempo de execução exponencial para solucioná-lo. 
(c) não existe algoritmo que o solucione, não importa quanto tempo seja disponibilizado.
(d) não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução polinomial que o
soluciona, fornecendo respostas aproximadas.
(e) não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução exponencial que
o soluciona, fornecendo respostas aproximadas.