Exercícios resolvidos sobre GLC e autômato com pilha do 2º/2012

Prévia do material em texto

Autoˆmatos e Computabilidade – Teste 3
Seja A o conjunto de cadeias de pareˆnteses apropriadamente encaixados. Construa uma grama´tica
livre-do-contexto na forma normal de Chomsky que gere A.
Resposta: A seguinte grama´tica gera A:
S → SS | (S) | ε
A forma normal de Chomsky e´:
S0 → SS | AX | AB | ε
S → SS | AX | AB
X → SB
A → (
B → )
Desenhe o diagrama de estados de um autoˆmato com pilha que reconhec¸a a linguagem
{02n1n|n ≥ 0}.
Resposta:
q0 q1 q3 q4
q2
ε,ε → $
0,ε → x 0,ε → ε
ε,ε → ε
1,x→ ε
ε,$→ ε
Desenhe o diagrama de estados de um autoˆmato com pilha que reconhec¸a a linguagem {w|w ∈
{0, 1}∗ e w conte´m a mesma quantidade de 0s e 1s}.
Resposta:
q0
q1
q4
0,ε → $
1,$ → ε
0,ε → 0
1,0→ ε
1,ε → $
0,$ → ε
1,ε → 1
0,1→ ε
Desenhe o diagrama de estados de um autoˆmato com pilha equivalente a` grama´tica livre-do-
contexto definida por
E → E + T | T
T → T x F | F
F → (E) | a
Resposta:
q0 q1 q2 q3
qa
qb
qc
qd
qe
qf
ε,ε → $ ε,ε → E
ε,E → F
ε,F → a
a,a→ ε
),)→ ε
(,(→ ε
+,+→ ε
x,x→ ε
ε,$→ ε
ε,E → T
ε,ε → +
ε,ε → E
ε,T → T
ε,ε → x
ε,ε → F
ε,F → (
ε,ε → E
ε,ε → )
Construa uma grama´tica livre-do-contexto que gere a linguagem {anb2ncm|m,n ≥ 0}.
Resposta:
S → TX
T → aTbb | ε
X → cX | ε
Desenhe o diagrama de estados de um autoˆmato com pilha que reconhec¸a a linguagem
{anb2ncm|m,n ≥ 0}.
Resposta:
q0 q1 q3 q4
q2
ε,ε → $
b,x→ ε b,ε → ε
ε,ε → ε
a,ε → x
ε,$→ ε
c,ε → ε
Seja L uma linguagem livre-do-contexto. Prove que L∗ tambe´m e´ livre-do-contexto.
Resposta: Se L e´ livre-do-contexto, existe uma grama´tica livre-do-contexto G = (V,Σ, R, S)
que a gera. Enta˜o, podemos construir uma grama´tica livre-do-contexto G′ que gera L∗ criando
uma nova varia´vel inicial S ′ /∈ V e adicionando a nova regra S ′ → S ′S | ε.
Seja o autoˆmato com pilha definido por P = ({q0,q1}, {a, b}, {x}, δ, q0, {q1}), onde a func¸a˜o de
transic¸a˜o δ esta´ definida por
δ(q0, a, ε) = {(q0, x)}
δ(q0, ε, ε) = {(q1, ε)}
δ(q1, b, x) = {(q1, ε)}
δ(q, x, y) = ∅ para todos os outros casos
Qual a linguagem reconhecida por P?
Resposta: {ambn|m ≥ n ≥ 0}.