Exercícios sobre autômato com pilha do 1º/2014

Prévia do material em texto

Autoˆmatos e Computabilidade – Teste 4
Considere a seguinte linguagem TROCO, que representa a equivaleˆncia de moedas de R$ 1 e
notas de R$ 2 com notas de R$ 5. O alfabeto da linguagem e´ Σ = {1, 2, 5, =}. Dada uma cadeia
w ∈ Σ∗, definimos |w|
a
como a quantidade de as em w, onde a e´ um elemento de Σ. Assim, se
w = 1121122=5=5, enta˜o |w|1 = 4, |w|2 = 3, |w|5 = 2, e |w|= = 2.
A linguagem TROCO esta´ definida por:
TROCO = {x=y| x ∈ {1, 2}∗, y ∈ {5}∗, |x|1 + 2 · |x|2 = 5 · |y|5},
Por exemplo, 1212212211=555 ∈ TROCO. Nessa cadeia, |x|1 = 5, |x|2 = 5 e |y|5 = 3, e a cadeia
representa o fato de que 5 moedas de R$ 1 mais 5 notas de R$ 2 equivalem a 3 notas de R$ 5.
Desenhe o diagrama de estados de um autoˆmato com pilha que reconhec¸a a linguagem TROCO.
Resposta:
q0 q1 q3 q8
q4
q5
q7
q6
q2
ε,ε → $
2,ε → x ε,ε → x
1, ε → x
ε,$ → ε
5, x → ε
ε, x → ε
ε, x → ε
ε, x → ε
ε, x → ε
=, ε → ε