Exercícios de Autômatos e Gramáticas

Prévia do material em texto

Nome: Lucas da Silva Pandagis 	Turma: CC5Q48 			RA: N601EA-0
1. (ENTREGAR). Construa o diagrama de um AFN-ε para a linguagem L1 = {w | w = 0*(1 + 2 + 3)} e = {0, 1, 2, 3}. 
Resposta: 
4. (ENTREGAR). Dado o AP definido por M3 = ({a, b, c, d}, {q0, q1, q2, q3, qf}, δ4, q0, {qf}, {1}) e δ4 é o diagrama abaixo:
Faça o passo a passo para a identificação da cadeia aabbcddd e mostre a cada passo o estado da pilha.
Resposta:
Fita a ser lida: aabbcddd
Passo 1: q0 = ler o símbolo “a”, não ler nada da pilha, gravar “1” na pilha:
Fita: aabbcddd
Pilha:
1
Passo 2: q0 = ler o símbolo “a”, não ler nada da pilha, gravar “1” na pilha:
Fita: aabbcddd
Pilha:
1
1
Passo 3: Vai para q1(condição (ε, ε, ε)) = ler o símbolo “b”, não ler nada da pilha, gravar “1” na pilha:
Fita: aabbcddd
Pilha:
1
1
1
Passo 4: q1 = ler o símbolo “b”, não ler nada da pilha, gravar “1” na pilha:
Fita: aabbcddd
Pilha:
1
1
1
1
Passo 5: Vai para q2(condição (ε, ε, ε)) = ler o símbolo “c”, ler o símbolo “1” da pilha, não gravar nada:
Fita: aabbcddd
Pilha:
1
1
1
Passo 6: Vai para q3(condição (ε, ε, ε)) = ler o símbolo “d”, ler o símbolo “1” da pilha, não gravar nada:
Fita: aabbcddd
Pilha:
1
1
Passo 7: q3 = ler o símbolo “d”, ler o símbolo “1” da pilha, não gravar nada:
Fita: aabbcddd
Pilha:
1
Passo 8: q3 = ler o símbolo “d”, ler o símbolo “1” da pilha, não gravar nada:
Fita: aabbcddd
Pilha: ε
Passo 9: Vai para qf (condição (?, ?, ε)) = Teste fita lida? Sim, Teste pilha vazia? Sim, não gravar nada.
5. (ENTREGAR). Dado o AFN-ε definido por M4 = ({a, b, c}, {q0, q1, q2, q3, q4, q5, qf}, δ5, q0, {qf}) e δ5 é o diagrama abaixo:
a. Faça sua conversão para um AFN utilizando a tabela de conversão com os Fechos-ε.
Resposta:
b. Descreva sua linguagem L5.
Resposta: 
L5 = {w | w = possui b como sufixo} e = {a, b, c}
8. (ENTREGAR). Dado a expressão regular (bb + cb) * c:
a. Desenvolva um AFN-ε a partir da expressão regular. 
Resposta:
b. Mostre a aplicação das cadeias bbc, cc e cbcb no AFN-ε criado e diga se elas são aceitas ou não.
Resposta: 
bbc: q0 (com ε vai para) q1 (com b vai para) q2 (com ε vai para) q3 (com b vai para) 
q4 (com ε vai para) q9 (com ε vai para) q10 (com c vai para) qf
Aceita a palavra bbc.
cc: q0 (com ε vai para) q5 (com c vai para) q6 (com ε vai para) q7 
cc não é aceita, para no q7, pois não possui um símbolo correspondente e ainda possuí o símbolo “c” para ser lido, e q8 também não é estado final.
cbcb: q0 (com ε vai para) q5 (com c vai para) q6 (com ε vai para) q7 (com b vai para) q8 (com ε vai para) q9 (com ε vai para) q10 (com c vai para) qf.
cbcb não é aceita, pois o AFN-ε da expressão só possibilita a escrita cbc e já chega no estado final, porém ainda falta um símbolo a ser lido.
9. (ENTREGAR). Dada a gramática G9 = ({S, A, B, C}, {a, b}, P, S) com conjunto P:
S AC | CB
A aA | ɛ
B Bb | ɛ
C aCb | a | b
a. Mostre a derivação das cadeias aaaaabb e aaabbbb. 
Resposta: 
aaaaabb: SACaACaaACaaaACaaaaACaaaaεC aaaaεaCb aaaaεabb = aaaaabb
aaabbbb: SCB aCbB aaCbbB aaaCbbbB aaabbbbB aaabbbbε = aaabbbb
b. Mostre a árvore de derivação da cadeia acima.