Gabarito Linguagens_Formais

Prévia do material em texto

Gabarito - Linguagens formais - 843 
 
1- Dada a Gramática Livre de Contexto abaixo 
S → AB | SCB 
A → aA | C 
B → bB | b C → cC | ɛ 
Converta-a para a Forma Normal de Chomsky. 
 
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 
 
Transformação para FNC: Etapa 1: 
S → AB | SCB | SB | CbB | b 
A → CaA | a | C cC | c 
B → CbB | b 
C → CcC | c 
Ca → a 
Cb → b 
Cc → c 
 
Transformação para FNC: Etapa 2: 
S → AB | SD1 | SB | C bB | b 
A → CaA | a | C cC | c 
B → CbB | b 
C → CcC | c 
Ca → a 
Cb → b 
Cc → c 
D1 → CB 
 
2- Dada a expressão regular (0v1)+101(0v1)*, apresente o seu 
respectivo autômato equivalente através da representação gráfica. 
 
3- 
import re 
#Retorna uma lista com todas as ocorrências da palavra 
"pa" 
txt = "Ana tem 20 anos e seu irmão Daniel tem 27 
anos. Juvenal, o avô deles, tem 77 anos e mora no apto 
17." 
x = re.findall("[A-Z]\w+", txt) print("Nomes: 
", x) 
x = re.findall("[0-9]* anos", txt) print(
"Idades: ", x) 
 
4- 1+3*5 
 
 
(1+3)*5 
 
 
import nltk 
grammar3 = nltk.CFG.fromstring(""" 
E -> N | A | S | M | D 
A -> E "+" E 
S -> E "-" E 
M -> E "*" E 
D -> E "/" E 
N -> Dig | Dig N 
Dig -> "0" | "1" | "2" |"3" |"4" |"5" |"6" |"7" |"8" 
|"9" """) 
rd_parser = nltk.parse.ShiftReduceParser(grammar3) 
texto = "5 * 1 + 3 * 5" .split() for p in 
rd_parser.parse(texto): print( p) 
 
 
 
 
 
5- 
Ps.: Só fiz a representação gráfica da máquina para o alfabeto de entrada 
para não ficar muito confuso. 
 
 
Esquece, eu refiz, e na minha opinião ficou uma porra 
 
Configuração inicial: 
 
... 0 0 1 0 1 1 ... 
 ↑ 
q0 
 
... x 0 1 0 1 1 ... 
 ↑ 
q2 
 
 
 
... x 0 1 0 1 1 ... 
 ↑ 
q2 
 
... x 0 y 0 1 1 ... 
 ↑ 
q3 
 
... x 0 y 0 1 1 ... 
 ↑ 
q3 
 
... x 0 y 0 1 1 ... 
 ↑ 
q0 
 
... x x y 0 1 1 ... 
 ↑ 
q2 
 
... x x y 0 1 1 ... 
 ↑ 
q2 
 
... x x y 0 1 1 ... 
 ↑ 
q2 
... x x y 0 y 1 ... 
 ↑ 
q3 
 
... x x y 0 y 1 ... 
 ↑ 
q3 
 
... x x y 0 y 1 ... 
 ↑ 
q3 
 
... x x y 0 y 1 ... 
 ↑ 
q3 
 
... x x y 0 y 1 ... 
 ↑ 
q3 
 
... x x y 0 y 1 ... 
 ↑ 
q0 
 
... x x y 0 y 1 ... 
 ↑ 
q0 
... x x y x y 1 ... 
 ↑ 
q2 
 
... x x y x y 1 ... 
 ↑ 
q2 
 
... x x y x y y ... 
 ↑ 
q3 
 
... x x y x y y ... 
 ↑ 
q3 
 
... x x y x y y ... 
 ↑ 
q0 
 
... x x y x y y ... 
 ↑ 
q0 
 
... x x y x y y ... 
 ↑ 
q0