gabarito_-_av3_-_Linguagens_Formais

Prévia do material em texto

QUESTÕES DISCURSIVAS 
GABARITO 
 
 
Questão 1 (2,0 pontos) 
 
 
 
SOLUÇÂO 
 
 
 
 
 
Questão 2 (2,0 pontos) 
 
 
 
<< SOLUÇÂO >> 
 
 
 
Questão 3 (2,0 pontos) 
 
 
 
<< SOLUÇÂO >> 
 
 
Eliminação de produções vazias: 
Vλ = {A, C} 
S → AB | SCB | SB | B 
A → aA | C | a 
B → bB | b 
C → cC | c 
Eliminação de produções unitárias: 
Fecho-S = {B} 
Fecho-A = {C} 
Fecho-B = ∅ 
Fecho-C = ∅ 
S → AB | SCB | SB | bB | b 
A → aA | a | cC | c 
B → bB | b 
C → cC | c 
Não existem símbolos inúteis. 
 
Transformação para FNC: 
Etapa 1: 
S → AB | SCB | SB | CbB | b 
A → CaA | a | CcC | c 
B → CbB | b C → CcC | c 
Ca → a 
Cb → b 
Cc → c 
Etapa 2: 
S → AB | SD1 | SB | CbB | b 
A → CaA | a | CcC | c 
B → CbB | b 
C → CcC | c 
Ca → a 
Cb → b 
Cc → c 
D1 → CB 
 
 
 
 
 
 
 
 
Questão 4 (2,0 pontos) 
 
 
 
 
 
<< SOLUÇÂO >> 
 
 
 
 
A linguagem do DFA é definida pela gramática G = (V, Σ, R, S0) com 
V = {S0, S1, S2}, Σ = {0, 1} e R sendo o seguinte conjunto de regras: 
S0 → 0S1 | 1S0 
S1 → 0S2 | 1S0 
S2 → 0S2 | 1S0 | ϵ 
 
 
Questão 5 (2,0 pontos) 
 
 
 
<< SOLUÇÃO >>