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

Prévia do material em texto

Autoˆmatos e Computabilidade – Teste 4
1. Considere cadeias da forma #w, onde w ∈ {0, 1}∗, ,e seja n = |w|. Desenhe uma ma´quina de
Turing que converta #w em #0n. Por exemplo, a ma´quina deve converter #01001 em #00000.
A ma´quina de Turing deve ir ao estado de aceitac¸a˜o imediatamente apo´s a conversa˜o, e deve
ir ao estado de rejeic¸a˜o se a cadeia de entrada na˜o tem a forma exigida. Na˜o precisa colocar
todas as transic¸o˜es que levam ao estado de rejeic¸a˜o.
Resposta:
q1 q2 qaceita# → D unionsq → E
1 → 0, D
0 → D
2. Suponha que representamos o nu´mero natural n pela cadeia 1n. Desenhe o diagrama de
estados de uma ma´quina de Turing que calcule f(n) = n+1 (por exemplo, f(111) = 1111).
A ma´quina de Turing deve ir ao estado de aceitac¸a˜o imediatamente apo´s a conversa˜o, e deve
ir ao estado de rejeic¸a˜o se a cadeia de entrada na˜o tem a forma exigida. Na˜o precisa colocar
todas as transic¸o˜es que levam ao estado de rejeic¸a˜o.
Resposta:
q1 qaceita
unionsq → 1, E
1 → D
3. Desenhe o diagrama de estados de uma ma´quina de Turing que reconhec¸a a linguagem 0∗,
sobre o alfabeto {0, 1}. Na˜o precisa colocar todas as transic¸o˜es que levam ao estado de
rejeic¸a˜o.
Resposta:
q1 qaceita
unionsq → E
0 → D
4. Desenhe o diagrama de estados de uma ma´quina de Turing que aceite somente as cadeias de
comprimento maior ou igual a 2, nas quais o primeiro s´ımbolo e´ diferente do u´ltimo s´ımbolo,
sobre o alfabeto {a, b}. Por exemplo, a ma´quina deve aceitar bbaba e ab, e deve rejeitar a,
bb e ababa. Na˜o precisa colocar todas as transic¸o˜es que levam ao estado de rejeic¸a˜o.
Resposta:
q1
q2 q3
q4 q5
qaceita
a → D
unionsq → E
a,b → D
b → D
b → D
unionsq → E
a,b → D
a → D
5. Suponha que representamos o nu´mero natural n pela cadeia 1n. Desenhe o diagrama de
estados de uma ma´quina de Turing que calcule f(n) = n−1 (por exemplo, f(111) = 11). A
ma´quina de Turing deve ir ao estado de aceitac¸a˜o imediatamente apo´s a conversa˜o, e deve
ir ao estado de rejeic¸a˜o se a cadeia de entrada na˜o tem a forma exigida. Na˜o precisa colocar
todas as transic¸o˜es que levam ao estado de rejeic¸a˜o.
Resposta:
q2 q3 qaceita
1 → unionsq, E
1 → D
unionsq → E