TA-T825-Linguagens Formais AV1

Prévia do material em texto

QUESTÕES OBJETIVAS E DISCURSIVAS 
 
PROVA AV1 – DISCIPLINA: LINGUAGENS FORMAIS – TURMA: 825 
 
1. A AV1 deve ser entregue individualmente no local apropriado do AVA 
2. As resoluções da atividade devem ser digitadas 
3. A atividade deve conter: 
1. Nome da disciplina 
2. Código da Turma 
3. Nome e matrícula do aluno 
4. A data de entrega é até 03/10/2020. 
5. A nota máxima dessa atividade é 7,0. 
6. Todas as respostas devem ter duas etapas explícitas: desenvolvimento e 
resultado. 
 
Questão 1 (1,0 ponto) 
 
Dada a expressão regular: (a v b)*(abb v a+b) 
Obtenha seu respectivo Autômato Finito Não-Determinístico: 
DESENVOLVIMENTO: 
(a v b)* → {λ, a, b, aa, ab, ba, bb, aaa, ...} 
(abb v a*b) → {b, ab, aab, abb, aaab, abbab, ...} 
 
Concatenando temos: 
{b, ab, bb, aab, abb, bbb, aaab, ...} 
 
RESULTADO: 
 
 
 
 
 
Questão 2 (1,4 ponto) 
 
Dado o AFN-ε abaixo: 
 
 
 
Faça a conversão para um AFN 
 
DESENVOLVIMENTO: 
 
 a b  
S0 S2 - S1 
S1 S3, S4 - - 
S2 - S3 - 
S3 - - - 
S4 S3 S3 - 
 
 
 Logo F’ = {S4} 
F(S0) = { S0, S1 } 
F(S1) = { S1 } 
F(S2) = { S2 } 
F(S3) = { S3} 
F(S4) = { S4 } 
 
 
 
• (S0, a) = ({S0}, a) 
= F ({R I R (S, a) ^ S ({S0, )}) 
= F ({R I R (S, a) ^ S{S0, S1}}) 
 
 
S = S0, (S0, a) = {S2} 
S = S1, (S1, a) = {S3, S4} 
 = F({S2, S3, S4}) 
 = F{S2} U F{S3} U F{S4} 
 = {S2, S3, S4} 
 
• (S0, b) = ({S0}, b) 
= F ({R I R (S, b) ^ S ({S0, )}) 
= F ({R I R (S, b) ^ S{S0, S1}}) 
 
 
S = S0, (S0, b) = { Ø } 
S = S1, (S1, b) = { Ø } 
 
 
 
• (S1, a) = ({S1}, a) 
= F ({R I R (S, a) ^ S ({S1, )}) 
= F ({R I R (S, a) ^ S{S1}}) 
 
 
S = S1, (S1, a) = {S3, S4} 
 = F{S3} U F{S4} 
 = {S3, S4} 
 
 
• (S1, b) = ({S1}, b) 
= F ({R I R (S, b) ^ S ({S1, )}) 
= F ({R I R (S, b) ^ S{S1}}) 
 
 
S = S1, (S1, b) = { Ø } 
 
 
• (S2, a) = ({S2}, a) 
= F ({R I R (S, a) ^ S ({S2, )}) 
= F ({R I R (S, a) ^ S{S2}}) 
 
 
S = S2, (S2, a) = { Ø } 
 
 
 
• (S2, b) = ({S2}, b) 
= F ({R I R (S, b) ^ S ({S2, )}) 
= F ({R I R (S, b) ^ S{S2}}) 
 
 
S = S2, (S2, b) = { s3 } 
 = F{S3} 
 = {S3} 
 
 
 
• (S3, a) = ({S3}, a) 
= F ({R I R (S, a) ^ S ({S3, )}) 
= F ({R I R (S, a) ^ S{S3}}) 
 
 
S = S3, (S3, a) = { Ø } 
 
 
 
• (S3, b) = ({S3}, b) 
= F ({R I R (S, b) ^ S ({S3, )}) 
= F ({R I R (S, b) ^ S{S3}}) 
 
 
S = S3, (S3, b) = { Ø } 
 
 
 
 
• (S4, a) = ({S3}, a) 
= F ({R I R (S, a) ^ S ({S4, )}) 
= F ({R I R (S, a) ^ S{S4}}) 
 
 
S = S4, (S4, a) = { S3 } 
 = F{S3} 
 = {S3} 
• (S4, b) = ({S3}, b) 
= F ({R I R (S, b) ^ S ({S4, )}) 
= F ({R I R (S, b) ^ S{S4}}) 
 
 
S = S4, (S4, a) = { S3 } 
 = F{S3} 
 = {S3} 
 
 
 a b 
S0 S2, S3, S4 - 
S1 S3, S4 - 
S2 - S3 
S3 - - 
S4 S3 S3 
 
 
 
 
RESULTADO: 
 
 
 
 
 
Questão 3 (1,4 ponto) 
 
Dado o AFD abaixo, 
 
 
 
 
construa sua respectiva gramática livre de contexto. 
 
DESENVOLVIMENTO: 
 
q0= S, q1= A, q2 = B 
 
S => 1S | 0A 
A => 1S | 0B 
B => 0S | 1B | ε 
 
RESULTADO: 
 
 
Questão 4 (1,4 ponto) 
 
Dada a gramática livre de contexto (GLC): 
S -> aS | bX | c 
X -> aX | bY | c 
Y -> aY | a 
 
Represente seu respectivo autômato. 
DESENVOLVIMENTO: 
 
 
 
 
RESULTADO: 
 
 
Questão 5 (1,4 ponto) 
Dada a gramática livre de contexto (GLC) com o T = { ε, c, “{”, “}” }: 
S -> { X 
X -> c X | } Y 
Y -> + S | ε 
 
Represente seu respectivo autômato e faça o processamento da palavra: {cc} + {c}. 
DESENVOLVIMENTO: 
 
 
 
 
 
{cc} + {c} 
 
 
 
{ c c } + { c } - 
>q1 q2 q2 q2 q3* q1 q2 q2 q3* 
 
 
 
 
 
 
Linguagens Formais – 825 
Vinícius Lima da Silva - 2018200264