AV1 - Linguagens Formais

Prévia do material em texto

AV1 – Trabalho Acadêmico 
Disciplina: Linguagens Formais 
Turma: 145 
Aluno: Gabriel da Silva Pinheiro // 2018101703 
Professor: Sérgio Assunção Monteiro 
 
AV1 – Linguagens Formais 
 
Questão 1 (3,0 pontos) 
 
Seja o alfabeto Σ= {0, 1} e uma expressão regular cuja linguagem pode ser representada 
por (Σ Σ Σ)*. Faça: 
 
(a) Apresente a respectiva expressão regular 
 
R.: ( (0, 1)(0, 1)(0, 1) )* 
 
(b) Obtenha o respectivo AFN com transições vazias 
 
R.: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
(c) Obtenha o respectivo AFN sem transições vazias 
 
 
R.: 
 
 
 
 
 
(d) Obtenha o respectivo AFD eliminando transições que não reconhecem palavras. 
 
 
R.: 
 
 
 
 
 
 
 
 
 
 
(e) Faça o processamento da palavra 011001 pelo AFD 
 
 
R.: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Palavra: 011001 // ACEITA 
 
Saída: abbabba 
 
 
 
 
 
Ciclo t0 t1 t2 t4 t5 t6 t7 
Entrada 0 1 1 0 0 1 - 
Estado e1 e2 e3 e1 e2 e3 e1 
Saída a b b a b b a 
(f) Faça o processamento da palavra ε (cadeia vazia) 
 
 
 
 
 
R.: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Palavra: Ε// ACEITA 
 
 
Questão 2: (3,0 pontos) 
 
Observe a gramática livre de contexto G = ({S, A, B, C}, {a, b, ε}, S, P), onde o conjunto 
P é dado por: 
 
S → AB | SCBA 
A → aAB | C 
B → bB | b 
C → cCA | ε 
 
Faça: 
(a) Obtenha a forma Normal de Chomsky. 
R.: 
Passo 1: Eliminação de produções vazias: 
 
 Vʎ {A, C} 
 
S → AB | SCBA | B | SB 
A → aAB | C | aB 
B → bB | b 
C → cCA | c 
 
 Passo 2: Eliminação de produções unitárias: 
Ciclo t0 t1 
Entrada Ε - 
Estado e1 e1 
Saída a a 
 
 Fecho-S = {B} 
 Fecho-A = {C} 
 Fecho-B = Ø 
 Fecho- C = Ø 
S → AB | SCBA | SB | bB | b 
A → aAB | aB | cC | c 
B → bB | b 
C → cCA | c 
 
Passo 3: Transformação para FNC: Etapa 1: 
 
S → AB | SCBA | SB | CbB | b 
A → CaAB | CaB | CcC | c 
B → CbB | b 
C → CcCA | c 
 Ca = a 
 Cb = b 
 Cc = c 
 
Passo 4: Transformação para FNC: Etapa 2: 
 
S → AB | SD1 | SB | CbB | b 
A → CaE1 | CaB | CcC | c 
B → CbB | b 
C → CcF1 | c 
 Ca = a 
 Cb = b 
 Cc = c 
 D1 = CBA 
 E1 = AB 
 F1 = CA 
 
 
(b) A GLC na forma normal de Chomsky é uma Gramática Regular? Em caso positivo, 
apresente uma justificativa. Caso negativo, justifique sua resposta. 
 
R.: Não, pois para a GLC na forma normal de Chomsky ser uma gramática regular 
ela deve ser linear, ou seja, ter apenas uma variável. Entretanto, isto é algo que a FNC 
não permite, pois para uma gramática estar em conformidade com a FNC ela deve ter 
“DUAS VARIÁVEIS” ou “UM SÍMBOLO TERMINAL”. 
Ex.: A -> BC 
 A -> b 
 Portanto, não é possível uma GLC na FNC ser uma Gramática Regular. 
 
Observação: pode usar o python e as bibliotecas vistas na aula, mas é necessário 
colocar o código no final do trabalho.