Doutor

Cap´ ıtulo 5. Gram´ticas Livres do Contexto a

5.7

Exerc´ ıcios

1. Considere a gram´tica, com produ¸˜es a co S −→ aSb | SS | λ. Mostre que a linguagem gerada por essa gram´tica ´ a e L = {w ∈ {a, b}∗ / Na (w) = Nb (w) e Na (v) ≥ Nb (v) para todo prefixo v de w}, e u a onde Na (w) ´ o n´mero de a’s, que ocorrem em w. Sugest˜o: testar as seguintes cadeias: abaabb, aabbaabb e ababab que fazemparte da linguagem e a cadeia aabbabba que n˜o faz a parte. 2. Desenhe a ´rvore de deriva¸˜o correspondente ao exerc´ anterior. a ca ıcio 3. Achar as gram´ticas livres do contexto para as seguintes linguagens (com m ≥ 1, n ≥ 1, a k ≥ 1 e p ≥ 1). (b) L = {an bm / n = 2m}, (a) L = {an bm / n = m − 1}, (c) L = {an bm / n ≤ m + 3},

(d) L = {an bm / 2m ≤ n + 1},

(e) L = {an bm ck / n = m ou m ≤k}, (f) L = {an bm ck / n = k ou n = m},

(h) L = {w ∈ {a, b}∗ / Na (w) ≥ Nb (w)}, (j) L = {ak bm an / m = 2n + k}, (i) L = {w ∈ {a, b}∗ / Na (w) ´ ´ e ımpar },

(g) L = {an bm ck / n = m ou m = k},

(k) L = {ak bm an / 2k = n + m},

(m) L = {ak bm an / m = 2(n + k) + 1}, (o) L = {ak bm an bp / m = k ou n = p}

(l) L = {ak bm an / k = 2n + m + 2},

(n) L = {ak bm an / n ´ par e k = m +n }, e 2 (p) L = {ak bm an bp / m = k ou n = p}

4. Desenhe uma gram´tica livre de contexto que gere todas as express˜es regulares v´lidas a o a sobre o alfabeto {a, b}. Por exemplo deve permitir gerar as cadeias (a + aa∗ b)∗ + (λ + aa)(bb)∗ b e (ab + ba)∗ (aa + bb)∗ . 5. Achar uma gram´tica livre do contexto para a linguagem a L = {an wwR bn / w ∈ {a, b}∗ , n ≥ 1}
Introdu¸ao ` Teoria daComputa¸ao: c˜ a c˜ Linguagens Formais, autˆmatos e Computabilidade o

137

5.7. Exerc´ ıcios 6. Defina uma gram´tica livre do contexto para a linguagem de todas cadeias no alfabeto a {a, b} que n˜o s˜o pal´ a a ındromos. Isto ´, para a linguagem e L = {w ∈ {a, b}∗ / w = wR } 7. Seja L = {an bn / n ≥ 0} (b) Mostre que Lk ´ livre do contexto, para cada k ≤ 1. e 8. Mostre uma ´rvore de deriva¸˜o paraa cadeia aabbbb, com a gram´tica a ca a S −→ AB | λ, A −→ aB, B −→ Sb. Dˆ uma descri¸˜o da linguagem gerada por essa gram´tica. e ca a 9. Considere a gram´tica com produ¸˜es a co S −→ aaB, A −→ bBb | λ, B −→ Aa. Mostre que a cadeia aabbabba n˜o est´ na linguagem gerada por tal gram´tica. a a a 10. Achar uma gram´tica livre do contexto para o conjunto de todas as express˜es regulares a o sobre oalfabeto {a, b}. 11. Mostre que a gram´tica seguinte ´ amb´ a e ıgua S −→ AB | aaB, A −→ a | Aa, B −→ b. 12. Construa uma gram´tica n˜o amb´ a a ıgua, equivalente ` gram´tica do exerc´ anterior. a a ıcio 13. Encontre uma S-gram´tica para L(aaa∗ b + b) e para L = {an bn / n ≥ 1}. a 14. Mostre que toda S-gram´tica ´ n˜o-amb´ a e a ıgua. 15. Mostre que a linguagem L = {w ∈ {a, b}∗ / Na (w) = Nb (w)} ´livre do contexto. e 16. Use o teorema 5.5.3, para remover produ¸˜es esquerda-recursivas nas gram´ticas co a (a) S −→ abS | SS | λ (a) Mostre que L2 ´ livre do contexto. e

(b) S −→ Sb | A, A −→ Aa | a

138

Introdu¸ao ` Teoria da Computa¸ao: c˜ a c˜ Linguagens Formais, autˆmatos e Computabilidade o

Cap´ ıtulo 5. Gram´ticas Livres do Contexto a (c) S −→ aZ | SbS, Z −→ aZb | λ. 17. Dˆuma gram´tica sem produ¸˜es esquerda-recursivas para a linguagem e a co L = {w ∈ {a, b}∗ / Na (w) > Nb (w)} 18. Elimine as produ¸˜es in´teis na seguinte gram´tica co u a S −→ a | aA | B | C, A −→ aB | λ, B −→ Aa, C −→ cCD, D −→ dd | ddD. 19. Elimine as λ-produ¸˜es de co S −→ AaB | aCaB, A −→ aBa | λ | B, B −→ bbA | λ, C −→ bbbC | AB. 20. Elimine as produ¸˜es unit´rias nas duas gram´ticas anteriores.co a a 21. Elimine produ¸˜es unit´rias, λ-produ¸˜es, produ¸˜es in´teis e produ¸˜es esquerda-recursivas co a co co u co nas seguintes gram´ticas livres do contexto: a (a) S −→ Sa | aAB A −→ B | aa | λ B −→ AbB | λ | C C −→ aCCa | ABC

(b) S −→ ASAS | B A −→ aAa | λ B −→ bB | C | Db C −→ aCb | ab D −→ Da | bD

(d) S −→ AbAaBa | ABSa | aAAbC, A −→ aAa | λ, B −→ bbB | BCa | aD | λ, C −→ cAE |...