nothnig

1. Mostre que a linguagem {an bn cn | n > 0} não é livre de contexto.
2. Seja G = (S, V, S, P) onde S = {a, b}, V = {S} e P é o seguinte conjunto de produções: S ® aSb
S ® aSa
S ® bSa
S ® bSb
S ® l
Mostre que L(G) é uma LLD.
3. Suponha que G = (S, V, S, P) seja uma GLC tal que cada produção em P ou é da forma A ® wB ou da forma A ® w, onde A, B Î V e w Î S*. L(G) é necessariamente uma LLD? Prove esta afirmação ou ache um contra-exemplo.
4. A forma normal de Chomsky diz que “qualquer linguagem livre de contexto
(LLC) pode ser gerada por uma gramática na qual todas as produções são da forma A ® BC ou A ® a, onde A, B e C são variáveis e a é um terminal.”
Considere a gramática
G = ({a, b, +, -, *, /, (, )}, {S, T, L}, S, P), onde P consiste das produções:
S ® T + S | T - S | T
T ® L * T | L/T | L
L ® (S) | a | b
Ache uma gramática na forma normal de Chomsky que gere L(G).
5. Dê um APN que aceite a linguagem dos parênteses casados pelo estado final.
6. Dê um APN que aceite pelo estado final a linguagem gerada pela GLC:
S ® aAA, A ® aS | bS | a
7. Converta a seguinte gramática à Forma Normal de Chomsky.
S ® 00A | B | 1
A ® 1AA ½ 2
2
B ® 0
8. Dê um APN de um estado que aceita a linguagem {wcwR | w Î (a + b)*}.
9. Dê um APN (autômato de pilha) que aceite a linguagem {wwR | w Î {0, 1}*} pela pilha vazia. Teste para 011110.
10. Considere a seguinte gramática sobre S = {a, b}, com símbolo inicial S:
S ® bA | aB; A ® a | aS | bAA; B ® b | bS | aBB ache uma gramática equivalente na forma normal de Chomsky.
11. Escreva a gramática para a linguagem com cadeias que contenham um único a a esquerda e n b’s a direita: abn, n > 0. Qual é o tipo desta linguagem?
12. Construa uma gramática livre de contexto G para a linguagem L(G) = { w = xayb | x, y Î {a, b}*}.
13. Mostre que para qualquer linguagem livre de contexto L, L – {l} também é livre de contexto.
14. Considere uma gramática G = (S, V, S, P), onde S = {0, 1}, V = {S}, P = {S ®
0S1, S