Propriedades das Linguagens Livres de Contexto

Prévia do material em texto

PROPRIEDADES DAS 
LINGUAGENS LIVRES DE 
CONTEXTO II 
Marcelo Guerra 
 
FORMA NORMAL DE CHOMSKY 
 Toda linguagem não vazia e sem e tem uma 
gramática G em que todas as produções tem uma 
das seguintes formas: 
 
1. A → BC, onde todos os símbolos são variáveis. 
 
2. A → a, onde ‘A’ é uma variável e ‘a’ um terminal. 
 
 Além disso, G não tem símbolos inúteis. 
 Dizemos, então, que tal gramática está na Forma 
Normal de Chomsky (FNC). 
 
 
FORMA NORMAL DE CHOMSKY 
Chomsky é o linguista que primeiro 
propôs as GLC como forma de descrever 
linguagens naturais. 
 Provou que toda GLC poderia ser convertida 
para Forma Normal de Chomsky (CNF). 
CNF apresenta vários usos: 
 Teste eficiente da pertinência de um string a 
uma LLC 
FORMA NORMAL DE CHOMSKY 
 Para converter uma gramática para a FNC 
 A gramática deve satisfazer as condições: 
 Não tem produções unitárias; 
 Não possui ε-produções; 
 Nem símbolos inúteis. 
 
 Toda produção terá a forma A → a, já permitida pela 
FNC ou terá um corpo de comprimento 2 ou mais. 
A. Organizar todos os corpos de comprimento 2 ou mais para que 
consistam apenas em variáveis. 
B. Desmembrar os corpos de comprimento 3 ou mais em uma 
cascata de produções, cada uma com um corpo que tem duas 
variáveis. 
 
FORMA NORMAL DE CHOMSKY 
 A construção da etapa (A) é dada por: 
 Para todo terminal a que aparecer em um corpo de 
comprimento 2 ou mais, crie uma nova variável A 
 Essa variável terá apenas a produção A → a 
 Usamos, então, A no lugar de a, em todos os corpos de 
comprimento  2 das produções onde a aparecer 
 
 Nesse ponto, toda produção terá um corpo que será 
um único terminal ou pelo menos duas variáveis e 
nenhum terminal. 
 
FORMA NORMAL DE CHOMSKY 
 Para a etapa (B), devemos desmembrar as 
produções A → B1B2...Bk para k  3 em um grupo 
de produções com duas variáveis no corpo. 
 
 Introduzimos k-2 novas variáveis, C1, C2,..., Ck-2 
 
 A produção original é trocada pelas k-1 produções 
 A → B1C1 
 C1 → B2C2 
 ... 
 Ck-3 → Bk-2Ck-2 
 Ck-2 → Bk-1Bk 
 
 
EXEMPLO 
 Converter a gramática abaixo para a FNC: 
 E → E + T 
 E → T * F 
 E → (E) 
 E → a | b | Ia | Ib | I0 | I1 
 T → T * F 
 T → (E) 
 T → a | b | Ia | Ib | I0 | I1 
 F → (E) 
 F → a | b | Ia | Ib | I0 | I1 
 I → a | b | Ia | Ib | I0 | I1 
 
EXEMPLO 
 Existem oito terminais que não aparecem 
sozinhos no corpo de uma produção. 
 Criamos oito variáveis novas e oito produções 
onde cada variável é substituída por seu 
terminal 
 A → a B → b 
 Z → 0 O → 1 
 P → + M → * 
 L → ( R → ) 
 
 
EXEMPLO 
 Se introduzirmos essas produções e substituirmos 
todo terminal em um corpo que seja diferente de um 
único terminal pela variável correspondente, 
obtemos: 
 
 E → EPT| TMF | LER| a | b | IA | IB |IZ | IO 
 T → TMF | LER| a | b | IA | IB |IZ | IO 
 F → LER| a | b | IA | IB |IZ | IO 
 I → a | b | IA | IB |IZ | IO 
 A → a 
 B → b 
 Z → 0 O → 1 
 P → + M → * 
 L → ( R → ) 
 
 
EXEMPLO 
 Agora, todas as produções estão na FNC exceto 
aquelas com tamanho 3: EPT, TMF e LER 
 
 Esses corpos aparecem em mais de uma produção 
 podemos lidar com um corpo de cada vez, 
introduzindo uma variável extra para cada um deles 
 
 Para EPT, introduzimos C1 e substituímos a 
única produção E → EPT por 
 E → EC1 
 C1 → PT 
 
EXEMPLO 
 Para TMF, introduzimos a nova variável C2 
 T → TC2 
 C2 → MF 
 As duas produções que usam esse corpo E → TMF e 
T → TMF são substituídas por: 
 E → TC2 
 T → TC2 
 C2 → MF 
O mesmo deve ser feito para LER. 
 Ex: F → LER 
 F → LC3 
 C3 → ER 
EXEMPLO 
E → EC1| TC2 | LC3| a | b | IA | IB |IZ | IO 
T → TC2 | LC3| a | b | IA | IB |IZ | IO 
F → LC3| a | b | IA | IB |IZ | IO 
I → a | b | IA | IB |IZ | IO 
A → a 
B → b 
Z → 0 
O → 1 
P → + 
M → * 
L → ( 
R → ) 
C1 → PT 
C2 → MF 
C3 → ER 
O resultado final da gramática na FNC é : 
 
TEOREMA 7.16 
 Se G é uma GLC cuja linguagem contém pelo 
menos um string diferente de ε, então existe uma 
gramática G1 na FNC tal que L(G1) = L(G) – {ε} 
EXERCÍCIO 7.1.2 
 S -> ASB | ε 
 A -> aAS | a 
 B -> SbS | A | bb 
 
a) Elimine as produções vazias 
b) Elimine as produções unitárias da gramática 
resultante. 
c) Elimine os símbolos inúteis da gramática resultante. 
d) Coloque a gramática resultante na forma normal de 
Chomsky.