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

Prévia do material em texto

Autoˆmatos e Computabilidade: Prova 2
1. (1 ponto) Fornec¸a a definic¸a˜o formal de grama´tica livre-do-contexto.
Resposta: Uma grama´tica livre-do-contexto e´ uma 4-upla (V,Σ, R, S), onde V e´ um con-
junto finito de varia´veis, Σ e´ um conjunto finito de terminais, disjunto de V , R e´ um conjunto
finito de regras, e S ∈ V e´ a varia´vel inicial. Cada regra tem a forma A → u, onde A ∈ V
e u ∈ (V ∪ Σ)∗.
2. (1 ponto) O que e´ uma grama´tica livre-do-contexto amb´ıgua? Responda e fornec¸a um
exemplo.
Resposta: Uma grama´tica livre-do-contexto amb´ıgua e´ aquela que gera alguma cadeia com
duas ou mais derivac¸o˜es mais a` esquerda diferentes ou, equivalentemente, com duas ou mais
a´rvores sinta´ticas diferentes.
Como exemplo, considere: S → S + S | S x S | a. A cadeia a + a x a e´ gerada com
duas derivac¸o˜es mais a esquerda diferentes:
(i) S ⇒ S + S ⇒ a + S ⇒ a + S x S ⇒ a + a x S ⇒ a + a x a.
(ii) S ⇒ S x S ⇒ S + S x S ⇒ a + S x S ⇒ a + a x S ⇒ a + a x a.
3. (1,5 pontos) Seja G uma GLC e b ≥ 2 o nu´mero ma´ximo de s´ımbolos no lado direito das
regras de G. Seja w uma cadeia gerada por G, de comprimento |w| ≥ bh+1. Prove que a
altura da a´rvore sinta´tica para w tem altura maior ou igual que h+ 1.
Resposta: Em qualquer a´rvore sinta´tica produzida por G, havera´ um ma´ximo de b folhas
a um passo da varia´vel inicial, um ma´ximo de b2 folhas a dois passos da varia´vel inicial, e
assim sucessivamente. Portanto, uma a´rvore de altura menor ou igual a h gera uma cadeia
de comprimento |w| ≤ bh. Equivalentemente, uma cadeia de comprimento |w| > bh, ou
|w| ≥ bh + 1, deve ser gerada por uma a´rvore de altura |w| > h, ou |w| ≥ h+ 1.
Resta mostrar que |w| ≥ bh+1 ⇒ |w| ≥ bh+1. Temos que, se b ≥ 2, enta˜o bh+1 = b · bh > bh.
Assim, bh+1 ≥ bh + 1.
4. (1 ponto) Seja uma ma´quina de Turing determin´ıstica com k fitasM = (Q,Σ,Γ, δ, q0, qaceita,
qrejeita). Escreva o domı´nio e o contradomı´nio da func¸a˜o de transic¸a˜o δ.
Resposta: O domı´nio e´ Q′ × Γk, onde Q′ = Q − {qaceita, qrejeita}. O contradomı´nio e´
Q× Γk × {E,D}k.
5. (1,5 pontos) Prove que toda linguagem decid´ıvel e´ enumera´vel em ordem lexicogra´fica.
Resposta: Se uma linguagem L e´ decid´ıvel, existe uma ma´quina de Turing D que a decide.
Seja Σ o alfabeto de L, e seja s1, s2, s3, . . . uma lista de todas as poss´ıveis cadeias sobre Σ,
em ordem lexicogra´fica. Podemos construir um enumerador em ordem lexicogra´fica para L,
da seguinte forma:
E= “Ignore a entrada:
1. Repita os seguintes passos para i = 1, 2, 3, . . .
2. Gere uma cadeias si ∈ Σ
∗.
3. Rode D sobre si.
4. Se D aceita, imprima si.”
6. (1 ponto) Considere a seguinte “prova” de que a intersec¸a˜o de duas linguagens livre-do-
contexto tambe´m e´ livre-do-contexto:
Sejam L1 e L2 linguagens livre-do-contexto. Definimos L = L1∩L2 = {w|w ∈ L1 e w ∈ L2}.
Assim, a linguagem L e´ um subconjunto de L1, pois w ∈ L⇒ w ∈ L1. Como L ⊆ L1 e L1
e´ livre-do-contexto, enta˜o L tambe´m deve ser livre-do-contexto.
No entanto, sabemos que a classe das linguagens livres-do-contexto na˜o e´ fechada sobre a
intersec¸a˜o. O que esta´ errado na “prova” acima? Justifique claramente sua resposta.
Resposta: O erro esta´ na u´ltima afirmac¸a˜o da prova. Um subconjunto de uma linguagem
livre-do-contexto na˜o e´ necessariamente tambe´m livre-do-contexto. Por exemplo, a lingua-
gem L = {ww|w ∈ Σ∗} e´ um subconjunto de Σ∗. No entanto, Σ∗ e´ livre-do-contexto,
enquanto L na˜o e´.
7. (1,5 pontos) Prove que a linguagem L = {an#a2n#a3n|n ≥ 0} na˜o e´ livre-do-contexto.
Resposta: Aplicamos o lema do bombeamento para LLCs. Suponha L livre-do-contexto, e
seja p seu comprimento de bombeamento. A cadeia s = ap#a2p#a3p ∈ L possui comprimento
6p+ 2 ≥ p e. Fazemos s = uvxyz, com |vxy| ≤ p e |vy| > 0. Considere dois casos:
(a) Se v ou y conte´m #, enta˜o uxz na˜o conte´m ambos #s. Portanto, uxz /∈ L.
(b) Se nem v nem y conteˆm #, enta˜o podemos escrever v = ai e y = aj, com 0 ≤ i ≤ p,
0 ≤ i ≤ p, e i+ j < 0.
i. Se vxy ocorre antes do segundo # em s, enta˜o uv2xy2z conte´m 3p+ i+ j as antes
do segundo # e somente 3p as depois dele. Por tanto, uv2xy2z /∈ L.
ii. Se vxy ocorre depois do primeiro # em s, enta˜o uv2xy2z conte´m 5p+i+j as depois
do primeiro # e somente p as antes dele. Por tanto, uv2xy2z /∈ L.
Todos os casos analisados criam uma contradic¸a˜o com o lema do bombeamento. Conclu´ımos,
enta˜o, que L na˜o e´ livre-do-contexto.
8. (1,5 pontos) Suponha que representamos o nu´mero natural n pela cadeia an. Desenhe o
diagrama de estados de uma ma´quina de Turing que calcule f(n) = 2n (por exemplo,
f(aaa) = aaaaaa). A ma´quina de Turing deve ir ao estado de aceitac¸a˜o imediatamente
apo´s escrever f(n) na fita, e deve ir ao estado de rejeic¸a˜o se a cadeia de entrada for a cadeia
vazia.
Inicialmente, a fita da ma´quina na˜o conte´m nenhum s´ımbolo especial (@ ou outros) no
extremo esquerdo. Coloque todos os estados e transic¸o˜es necessa´rias, na˜o utilize blocos
representando outras ma´quinas de Turing como “sub-programas”. As transic¸o˜es que levam
ao estado de rejeic¸a˜o podem ser omitidas.
Resposta:
q0 q1 q2
q3
qaceita
a→ #,D
¬⊔ → D
⊔ → x,E
¬#→ E
#→ a,D
x→ a,D
x→ a,D
⊔ → E