2ª Prova de Autômatos e Computabilidade - 2º/2015 - Lucero - UnB

Prévia do material em texto

Autoˆmatos e Computabilidade: Prova 2
Prof. Jorge C. Lucero
4 de outubro de 2015
Nome: Matr´ıcula:
1. (a) (1 ponto) Defina o que e´ a forma normal de Chomsky para uma grama´tica livre-do-
contexto.
Reposta: Uma grama´tica livre-do-contexto G esta´ na forma normal de Chomsky se
todas suas regras sa˜o da forma: A → BC, A → a ou S → ε, onde A, B e C sa˜o
varia´veis, S e´ a varia´vel inicial, B e C sa˜o diferentes da varia´vel inicial e a e´ um
terminal.
(b) (1 ponto) Explique como utilizar a forma normal de Chomsky para determinar se uma
cadeia w pertence a` linguagem de uma grama´tica livre-do-contexto G.
Reposta: Uma grama´tica livre-do-contexto na forma normal de Chomsky gera uma
cadeia de comprimento n em exatamente 2n − 1 passos, se n ≥ 1, ou um passo, se
n = 0. Enta˜o, para determinar se uma cadeia w dada pertence a L(G) podemos,
primeiro, converter G a` forma normal de Chomsky. Seguidamente, listamos todas as
cadeias geradas pela forma normal em 2n − 1 passos, onde n = |w|, se n ≥ 1; ou um
passo, se n = 0. Se w esta´ nessa lista, enta˜o w ∈ L(G); se na˜o esta´, enta˜o w /∈ L(G).
2. (2 pontos) Explique como obter uma grama´tica livre-do-contexto G = (V,Σ, R, S) equiva-
lente a um autoˆmato com pilha P = (Q,Σ,Γ, δ, q0, F ) dado.
Reposta: G pode ser constru´ıda seguindo os seguintes passos.
(a) Modifique P de forma que possua um u´nico estado de aceitac¸a˜o, esvazie a pilha antes
de aceitar uma cadeia, e cada transic¸a˜o empilhe ou desempilhe um s´ımbolo, mas na˜o
ambos.
(b) Para cada par de estados p, q crie a varia´vel Apq.
(c) Para cada par de transic¸o˜es (s, c) ∈ δ(p, a, ε) e (q, ε) ∈ δ(t, b, d) adicione a regra
Apq → AprArq, para todo estado r ∈ Q.
(d) Para cada par de transic¸o˜es (s, c) ∈ δ(p, a, ε) e (q, ε) ∈ δ(t, b, c) adicione a regra
Apq → aAstb.
(e) Para cada estado p adicione a regra App → ε.
(f) Fac¸a a varia´vel inicial Aq0qaceita , onde q0 e´ o estado iniciale e qaceita e´ o estado de acei-
tac¸a˜o.
3. Para cada uma das seguintes linguagens, determine se sa˜o livres-do-contexto ou na˜o e prove
sua resposta.
(a) (1 ponto) {w#x| x, w ∈ {a, b}∗ e wR e´ uma subcadeia de x}.
Reposta: A linguagem e´ livre-do-contexto. O seguinte autoˆmato com pilha a reco-
nhece:
q0 q1 q2 q3 q4
ε,ε→ $
a,ε→ a
b,ε→ b
#,ε→ ε
a,ε→ ε
b,ε→ ε
ε,ε→ ε
a,a→ ε
b,b→ ε
ε,$→ ε
a,ε→ ε
b,ε→ ε
Tambe´m, a linguagem e´ gerada pela seguinte grama´tica livre-do-contexto:
S → WT
W → aWa | bWb | #T
T → aT | bT | ε
(b) (1 ponto) {anbman|n > m ≥ 0}.
Reposta: A linguagem na˜o e´ livre-do-contexto.
Aplicac¸a˜o do lema do bombeamento: Suponha que a linguagem dada (L) e´ livre-do-contexto,
e seja p seu comprimento de bombeamento. Considere a cadeia de teste s = ap+1bpap+1.
Note que s ∈ L e |s| = 3p + 2 ≥ p. Fac¸a s = uvxyz, com |vxy| ≤ p e |vy| > 0. Existem as
seguintes possibilidades para vy:
(a) Se vy conte´m somente 0 < k ≤ p as da primeira sequeˆncia de as, enta˜o, uv0xy0z =
ap+1−kbpap+1 /∈ L, pois as quantidades de as ambas sequeˆncias de as sa˜o diferentes.
(b) Se vy conte´m somente 0 < k ≤ p bs, enta˜o, uv2xy2z = ap+1bp+kap+1 /∈ L, pois a
quantidade de bs na˜o e´ menor que a quantidade de as na primeira ou na segunda
sequeˆncia de as.
(c) Se vy conte´m somente 0 < k ≤ p as da segunda sequeˆncia de as, enta˜o, uv0xy0z =
ap+1bpap+1−k /∈ L, pois as quantidades de as ambas sequeˆncias de as sa˜o diferentes.
(d) Se vy conte´m k > 0 as da primeira sequeˆncia de as e ℓ > 0 bs, com k + ℓ ≤ p, enta˜o,
uv2xy2z = ap+k+1bp+ℓap+1 /∈ L, pois as quantidades de as ambas sequeˆncias de as sa˜o
diferentes.
(e) Se vy conte´m k > 0 as da segunda sequeˆncia de as e ℓ > 0 bs, com k + ℓ ≤ p, enta˜o,
uv2xy2z = ap+1bp+ℓap+k+1 /∈ L, pois as quantidades de as ambas sequeˆncias de as sa˜o
diferentes.
Conclu´ımos que L viola o lema do bombeamento, o que implica que na˜o e´ livre-do-contexto.
4. (1 ponto) Desenhe o diagrama de estados de uma ma´quina de Turing que reconhec¸a mas
na˜o decida a linguagem {w|w ∈ {a, b}∗e w conte´m pelo menos um a}. Essa linguagem e´
indecid´ıvel?
Resposta: A seguinte ma´quina de Turing reconhece a linguagem dada. No entanto, na˜o a
decide pois “entra em loop” sobre qualquer cadeia que na˜o contenha o s´ımbolo a.
q0 qaceita
a→ D
b→ D
⊔ → D
A linguagem e´ decid´ıvel. A seguinte ma´quina de Turing a decide:
q0 qaceita
qrejeita
a→ D
b→ D
⊔ → D
5. (2 pontos) Prove que uma linguagem e´ decid´ıvel se e somente se e´ enumera´vel em ordem
lexicogra´fica. Na sua prova, pode supor que existe uma ma´quina de Turing ENUM que enu-
mera todas as cadeia sobre um alfabeto Σ em ordem lexicoga´fica. Para descrever ma´quinas
de Turing utilize o formato:
M= “Sobre a cadeia de entrada . . .:
1....
2....
...
Reposta:
(a) Provamos que se uma linguagem L e´ decid´ıvel, enta˜o e´ enumeravel em ordem lexico-
gra´fica. Suponha L decid´ıvel e seja M a ma´quina de Turing que a decide. Enta˜o, a
seguinte ma´quina de Turing enumera L em ordem lexicogra´fica.
E= “Ignore a entrada:
1. Rode ENUM para gerar cadeias s1, s2, s3, . . . ∈ Σ
∗ em ordem lexicogra´fica.
A cada cadeia gerada si:
2. Rode M sobre si. Se aceita, imprima si.”
(b) Provamos que se uma linguagem L e´ e´ enumeravel em ordem lexicogra´fica, enta˜o e´
decid´ıvel. Suponha L enumera´vel em ordem lexicogra´fica e seja E a ma´quina de Turing
que a enumera. Enta˜o, a seguinte ma´quina de Turing decide L:
M= “Sobre a cadeia de entrada w:
1. Rode E para gerar cadeias s1, s2, s3, . . . ∈ L. A cada cadeia gerada si:
2. Compare w e si. Se w = si, aceite; se w < si, rejeite.”
6. (1 ponto) Verdadeiro ou falso? Justifique brevemente sua resposta.
(a) O complemento de toda linguagem livre-do-contexto na˜o e´ livre-do-contexto.
Resposta: Falso. As linguagens ∅ e Σ∗, onde Σ e´ um alfabeto, sa˜o complementos uma
da outra, e ambas sa˜o livres-do-contexto.
(b) Toda linguagem regular e´ livre-do-contexto.
Resposta: Verdadeiro. Se uma linguagem L e´ regular, enta˜o existe um autoˆmato
finito que a reconhece. Todo autoˆmato finito pode ser considerado como um autoˆmato
com pilha que ignora sua pilha.