Linguagens Formais e Automatos

Prévia do material em texto

Exercícios 
1. Desenhe o diagrama de estados de um autômato finito determinístico para cada uma 
das linguagens abaixo. 
a. {w | w é qualquer palavra, exceto 0, 11, 011, 1011} 
b. {w | w tem comprimento ímpar ou termina em 11} 
c. {w | w começa em 1 ou termina em 0 ou tem comprimento par} 
d. {w | w começa e termina em 1 e contém pelo menos três 0s} 
e. {w | w começa em 2 e contém pelo menos dois 0s e um 1} 
f. {w | w é um número binário divisível por 3} 
2. Construa o DFA mínimo M que aceita L(N), a partir do NFA N = ( {q0,q1,q2}, {0,1}, δ, 
q0,{q1} ) onde δ(q0,0) = {q0, q1}, δ(q1,1) = {q1, q2}, δ(q2,ε) = {q0}. 
3. Considere um Autômato Finito Determinístico M = ( {q0,q1,q2,q3,q4,q5}, {a,b}, δ, 
q0,{q2,q3} ) onde δ: 
 
4. Mostre usando o lema do bombeamento que as seguintes linguagens não são 
regulares 
a. 𝐴 = {𝑥 1𝑛 |𝑛 ≥ 0, 𝑥 ∈ {0, 1}∗ 𝑒 |𝑥| = 𝑛} 
b. A = {a bn cn | n ≥ 0} 
5. Descreva gramáticas Livres de Contexto que geram as seguintes linguagens, todas 
sobre o alfabeto {0, 1}. 
a. {w | w contém pelo menos três 0s} 
b. {w | |w| é ímpar e o símbolo do meio é o 1} 
c. {0r 1s 0t | r, s, t ≥ 0 e s = r+t} 
6. Considere as gramáticas abaixo. Para cada uma, especifique a linguagem gerada e 
simplifique-a, se necessário. 
a. G1 = ({S,A}, {a,b}, S, P1), onde P1 = {S→a | A | SS, A → a} 
b. G2 = ({S,A}, {a,b}, S, P2), onde P2 = {S→aSa | bSb | aAb | bAa, A → aA | 
bA | λ} 
c. G3 = ({S,A,B}, {a,b}, S, P3), onde P3 = {S→aS | AB, A → bA, B→ AA} 
d. G4 = ({S,A,B}, {a,b}, S, P6), onde P6 = {S→ aBS | bAS | λ, A → bAA | a, 
B→ aBB | b} 
e. G5 = ({S,A,B}, {a,b,c,d}, S, P7), onde P7 = {S→ABd, A → aAb | λ, B→ 
bBc | λ} 
f. G6 = ({S,A,B,C,D,F}, {a,b,c,d}, S, P10), onde P10 = {S→aAbB | cdC | E, 
A → A | Bc , B→dA | cBdc, C→abEDd | Eabc | acDb, D → Dac | cDa | acd, 
E → aBbAc | λ, F → CCc} 
7. Represente autômatos com pilha que reconheçam as linguagens do Exercício anterior 
através de diagramas de estados. 
8. Considere a seguinte gramática G = ({S}, {a,b}, S, P), onde P = { S→SS | aSa | bSb | λ } 
a. Qual a linguagem gerada? 
b. A gramática é ambígua? 
c. Para a palavra aabbaaaa: 
i. Construa uma árvore de derivação 
ii. Para a árvore construída, determine as derivações mais à esquerda e a 
mais à direita. 
9. Remover regras-ε e regras em cadeia mantendo a gramática equivalente 
a. S → AB|BCS 
A → aA|C 
B → bbB|b 
C → cC|ε 
b. S → aS|bS|B 
B → bb|C|ε 
C → cC|ε 
10. Remover símbolos inúteis 
a. S → AA|CD|bB 
A → aA|a 
B → bB|bC 
C → cB 
D → dD|d 
b. S → ACH|BB 
A → aA|aF 
B → CFH|b 
C → aC|DH 
D → aD|BD|Ca 
F → bB|b 
H → dH|d 
11. Considere as gramáticas abaixo. Converta-as para as Formas Normais de Chomsky e 
Greibach 
a. G1 = ({S}, {a,b}, S, {S → aSb | ab }) 
b. G2 = ({S}, {a,b,c}, S, {S → aSa | bSb | c }) 
c. G3 = ({S}, {a,b,c}, S, {S → aSbSc | ab | bc }) 
d. G4 = ({S}, {a,b,c,d}, S, {S → aSb | aSc | d }) 
e. G5 = ({S, A, B}, {a,b}, S, {S → ABb|a, A → aaA|B, B →bAb}) 
f. G6 = ({S, A, B, C}, {a,b,c}, S, {S → AaBab|abCc, A → aAc|Bc, B → bAb| bbc, 
C→ab | ac | bc }) 
12. Dadas as seguintes gramáticas, usando o algoritmo de CYK: 
 
a. Verifique se a cadeia abaabb pertence à linguagem L(G1) 
b. Verifique se a cadeia ababb pertence à linguagem L(G1) 
c. Verifique se a cadeia aabaa pertence à linguagem L(G2) 
d. Verifique se a cadeia aaba pertence à linguagem L(G2) 
e. Verifique se a cadeia aabaaa pertence à linguagem L(G2) 
f. Verifique se a cadeia bbbb pertence à linguagem L(G2) 
g. Verifique se a cadeia acaca pertence à linguagem L(G3) 
h. Verifique se a cadeia abbca pertence à linguagem L(G3)