Exercícios sobre máquina de Turing do 1º/2013

Prévia do material em texto

Autoˆmatos e Computabilidade – Teste 4
Desenhe o diagrama de estados de uma ma´quina de Turing que, dada uma cadeia de entrada
w ∈ {a, b}∗, concatene o reverso de w a` direita da entrada w e pare. Por exemplo, se a fita
inicialmente conte´m aababb, quando a ma´quina de Turing pare a fita devera´ conter aababbbbabaa.
Atenc¸a˜o: a ma´quina de Turing recebe, como entrada, somente a cadeia w, sem nenhum marcador
no extremo esquerdo da fita. Coloque todos os estados necessa´rios, na˜o utilize blocos represen-
tando outras ma´quinas de Turing como “sub-programas”.
Resposta:
q0q1 q3q2 q4
q5
qacc
a→ x,D
¬⊔ → D
⊔ →
•
a,E
¬x→ E
x→ a,D
b→ x,D
¬⊔ → D
⊔ →
•
b,E
¬x→ E
x→ b,D
•
a→ a,D
•
b→ b,D
•
a→ a,D
•
b→ b,D
⊔ → E
⊔ → E
Desenhe o diagrama de estados de uma ma´quina de Turing que, dada uma cadeia de entrada
w ∈ {a, b}∗, remova todos os bs e pare. Por exemplo, se a fita inicialmente conte´m aababba,
quando a ma´quina de Turing pare a fita devera´ conter aaaa (e na˜o aa ⊔ a ⊔ ⊔a).
Atenc¸a˜o: a ma´quina de Turing recebe, como entrada, somente a cadeia w, sem nenhum marcador
no extremo esquerdo da fita. Coloque todos os estados necessa´rios, na˜o utilize blocos represen-
tando outras ma´quinas de Turing como “sub-programas”.
Resposta:
q0 q1 q2 q3
q4
qacc
a→ D
b→ x,D
¬⊔ → D
⊔ → E
b→ E
a→ b,E
¬x→ E
x→ a,D
x→ ⊔,D
b→ ⊔,D
⊔ → E
⊔ → E
Desenhe o diagrama de estados de uma ma´quina de Turing que decida a linguagem {anbm| 0 ≤
n < m}.
Resposta:
q0 q1 q2
q3
qacc
a→
•
a,D
a→ D
•
b→ D
b→
•
b,E a→ E
•
b→ E
•
a→ D
b→ E
•
b→ E
b→ E
•
b→ E
⊔ → E
Desenhe o diagrama de estados de uma ma´quina de Turing que decida a linguagem {wcwcw|w ∈
{a, b}∗}.
Resposta:
q0
q1 q2 q3 q4
q5
q6 q7 q8 q9
q10
q11
qacc
a→ x,D
a→ D
b→ D
c→ D
y→ D
a→ y,D
a→ D
b→ D
c→ D
z→ D
a→ z,D
b→ x,D
a→ D
b→ D
c→ D
y→ D
b→ y,D
a→ D
b→ D
c→ D
z→ D
b→ z,D
¬x→ E
x→ D
c→ D
y→ D
c→ D
z→ D
⊔ → E