AV1 - Linguagens Formais

Prévia do material em texto

QUESTÕES OBJETIVAS E DISCURSIVAS 
 
PROVA AV1 – DISCIPLINA: LINGUAGENS FORMAIS 
 
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: 
RESULTADO: 
 
 
Questão 2 (1,4 ponto) 
Dado o AFN-ε abaixo: 
 
 
Faça a conversão para um AFN 
 
DESENVOLVIMENTO: 
Fechos: 
Fϵ(S0) = {S0, S1} 
Fϵ(S1) = {S1} 
Fϵ(S2) = {S2} 
Fϵ(S3) = {S3} 
Fϵ(S4) = {S4} ​�​ F’ 
 
Nenhum dos fechos possui o estado final S4 além do próprio ​Fϵ(S4)​, logo apenas S4 
continuará sendo um estado final. 
 
Transações atuais: 
ʆ a b ε 
S0 S2 --- S1 
S1 {S3, S4} --- --- 
S2 --- S3 --- 
S3 --- --- --- 
S4 S3 S3 --- 
 
 
ʆ ‘ (S0, a): Fϵ(S0) = {S0, S1} 
 ʆ(S0, a) = S2 ​�​ Fϵ(S2) = {S2} 
 ʆ(S1, a) = S3, S4 ​�​ Fϵ(S3) = {S3} e Fϵ(S4) = {S4} 
ʆ ‘ (S0, a): Fϵ(S2) = {S2}, Fϵ(S3) = {S3} e Fϵ(S4) = {S4} 
 
 
ʆ ‘ (S0, b): Fϵ(S0) = {S0, S1} 
 ʆ(S0, b) = Não possui 
 ʆ(S1, b) = Não possui 
ʆ ‘ (S0, b): Não possui 
 
ʆ ‘ (S1, a): Fϵ(S1) = {S1} 
ʆ(S1, a) = S3, S4 ​�​ Fϵ(S3) = {S3} e Fϵ(S4) = {S4} 
ʆ ‘ (S1, a): Fϵ(S3) = {S3} e Fϵ(S4) = {S4} 
 
ʆ ‘ (S1, b): Fϵ(S1) = {S1} 
ʆ(S1, b) = Não possui 
ʆ ‘ (S1, b): Não possui 
 
ʆ ‘ (S2, a): Fϵ(S2) = {S2} 
ʆ(S2, a) = Não possui 
ʆ ‘ (S2, a): Não possui 
 
 
ʆ ‘ (S2, b): Fϵ(S2) = {S2} 
ʆ(S2, b) = S3 ​�​ Fϵ(S3) = {S3} 
ʆ ‘ (S2, b): Fϵ(S3) = {S3} 
 
ʆ ‘ (S3, a): Fϵ(S3) = {S3} 
ʆ(S3, a) = Não possui 
ʆ ‘ (S3, a): Não possui 
 
ʆ ‘ (S3, b): Fϵ(S3) = {S3} 
ʆ(S3, b) = Não possui 
ʆ ‘ (S3, b): Não possui 
 
ʆ ‘ (S4, a): Fϵ(S4) = {S4} 
ʆ(S4, a) = S3 ​�​ Fϵ(S3) = {S3} 
ʆ ‘ (S4, a): Fϵ(S3) = {S3} 
 
ʆ ‘ (S4, b): Fϵ(S4) = {S4} 
ʆ(S4, b) = S3 ​�​ Fϵ(S3) = {S3} 
ʆ ‘ (S4, b): Fϵ(S3) = {S3} 
 
Transações para o novo autômato: 
ʆ ‘ 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: 
RESULTADO: 
S=q0; A=q1; B=q2 
G = ({S, A ,B}, {0,1}, P, S) 
P: S ​�​ 1S | 0A 
P: A ​�​ 1S | 0B 
P: B ​�​ 1B | 0S | ε 
 
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: 
S = q0; X = q1; Y = q2; sendo q3 e q4 estados mortos; 
 
 
 
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: 
RESULTADO: 
S = q0; X = q1; Y = q2; 
 
 
 
Processamento da palavra: {cc} + {c} 
 
Elemento { c c } + { c } --- 
Estado q0 q1 q1 q1 q2 q0 q1 q1 q2