Resumo Forma Normal de Chomsky

Prévia do material em texto

Às vezes quando temos uma gramática ambígua podemos encontrar uma gra­
mática não-ambígua que gera a mesma linguagem. Algumas linguagen� livrês­
do-contexto, entretanto, podem ser geradas apenas por gramáticas ambíguas. 
Tais linguagens são chamadas inerentemente ambíguas. O Problema 2.29 pede 
que você prove que a linguagem { aibj ck I i = j ou j = k} é inerentemente 
ambígua. 
FORMA NORMAL DE CHOMSKY 
Quando se trabalha com linguagens livres-do-contexto, � freqüentemerite con­
veniente tê-las em forma simplificada. Uma das formas mais simples e mais 
. úteis é chamada forma normal de Chomsky. A forma normal de Chomsky é útil 
quando se quer dar a(goritmos para trabalhar com gramáticas livres-do-contexto, 
como fazemos nos Capítulos 4 e 7. 
DEFINIÇÃO 2.8
.:- � 
Uma gramática livre-do-contexto está na forma normal de
Chomsky se toda regra é da forma 
A-) BC 
A -) a 
onde a é qualquer terminal e A, B e C são quaisquer variáveis -
exceto que B e C não podem ser a variável inicial. Adicionalmente, 
permitimos a regra S -+ ê, ond_e Sé a variável inicial. 
TEOREMA 2.9 ...................................................................................................._ 
Qualquer li11guagem livre-do-contexto é gerada por uma gramática lm:e-do­
cont�xto p.a forma normal de Chomsky. 
Professor
Retângulo
Professor
Nota
Unmarked definida por Professor
r VA Pocl(•1110. ·oi1v ·n ·r qunl<Jt1 'l' l'l'flrnr.tica (} rrn forma nor-
.hom�k . A ·onv ·r:no t 'Ili víirios ·suírrio., li< • qw,iii nt; r ·gr:1 11 que vfr>lam 
uli 'tl' �,o snhst it nídn, por rc rnrn ·q11ivnl 'lll •:; <JII<� .,� ntfr:fo 6ria.,. Pri-
n,,•,rw·l . di ·i m:\m ). \11\Hl no :l V;lrÍ:Ív ·1 ini ·inl. Então, climirinmon ocl::i., a., regras 
fonnn A -> . ') :unh �111 ·li111i1rn1110s Lodos ns rcgrn uniuíritJs da forma 
. t / . • m :unho. os nsos, ·orrigimos o 11rn111:iti ·a para gnrnntir que ela ainda 
"rc n m . ma lin rng m. 1• innlmcnlc, e 11vcrtcmo0 n r!,!gras rcmancsc:cntcs na 
fi nna :tpr pri:tdn . 
. 
PROVA Primeiro, adicionamos uma nova variável inicial 80.� a regra So ➔ 8,
na qual era :1 variável inicial original. Essa mudança garante que a variável 
inicial não ocorre no lado direito de uma regra. 
· Segundo, cuidamos de todas as regras e. Removemos uma regra e, A➔ e, em
que A não é a variável inicial. Então, para cada ocorrência de A no lado direito
de uma regra, adicionamos uma nova regra com essa ocorrência apagada. Em
outras palavras, se R--+ uAv é uma regra na qual u e v são cadeias de variáveis e
terminais, adicionamos a regra R ➔ uv. Fazemos isso para cada ocorrência de A,
de modo que a regra R ➔ uAvAw nos·leva·a adicionar R ➔ uvAw, R ➔ uAvw
e R ➔ uvw. Se tivermos a regra R ➔ A, adicionamos R ➔ · e a menos que
tivéssemos previamente removido a regra R ➔ e. Repetimos esses passos até
que eliminemos todas as regras e que não envolvem a variável inicial.
Terceiro, lidamos com todas as regras unitárias. Removemos uma regra uni­
tária A ➔ B. E:0:tão, sempre que uma regra B ➔ u aparece, adicionamos a regra 
A ➔ u, a menos que isso tenha sido uma regra unitária previamente removida. 
Como antes, u é uma cadeia de variáveis e terminais. Repetimos esses passos até 
que eliminemos todas as regras unitárias. 
Finalmente, convertemos todas as regras remanescentes para a forma apro­
priada. Substituímos cada regra A ➔ u1 u2 · · · uk, onde k > 3 e cada Ui é uma 
variável ou símbolo terminal, pelas regras A -4 u1A1, A1 ➔ u2A2, A2 ➔ u3A3,
... , e Ak-2 ➔ Uk-l uk '. Os Ais são novas variáveis. Se k = 2, substituímos 
qualquer terminal Ui na(s) regra(s) precedente(s) com a nova variável Ui e adi­
cionamos a regra Ui➔ Ui, 
.......................................................................................................................................................................... .. 
EXEMPLO 2.10 ......................................................................................................................... .
Suponha que G6 seja a GLC abaixo e converta-a para a forma normal de Chomsky 
usando o procedimento de conversão que acaba de ser dado. A série de gramá­
ticas apresentadas ilustra os passos na conversão_- As re.gras mostradas em negrito 
acabaram de ser adicionadas. As regras mostradas em cinza (como em "ci·nz:a")
acabaram de ser removidas. 
1. A GLC original G6 é mostrada à esquerda. O resultado de se aplicar.o pri­
mciro passo para introduzir uma nova variável inicial aparece à direita.
So -► S 
ASAlalJ 
A -►DIS 
D -► b I ê
2. Remova as regras E n ➔ E, mostrado à esquerda e A ➔ e mostratlo à
direita.
' ' 
So '➔ S
S ➔ ASAI aB la 
A ➔ BISle 
B➔blê 
So ➔ S 
··s ➔ ASAI aB I a I SA I AS I S
A ➔ BISle
B➔b
3a.. Remova regras unitárias S ➔ S, mostrado à esquerda, e·S0 ➔ S, mostrado 
à direita. 
So ➔ S 
S -+ ASAI aB I a I SA I AS 1 8 
A ➔ BIS 
B-+ b' 
So -+ S I ASA I aB Ia I SA I AS
S ➔ .ASA I aB I a I SA I AS 
A-+BIS 
B ➔ b 
3b. · Remova as regras unitárias A ➔ B e A ➔ S. 
�� 
So ➔ ASA I aB I a I SA I AS 
S ➔ ASA I aB ! a I SA I AS 
A➔ BISlb 
So-+ AMd an·1 a 1 .SAI AS 
S ➔ AM I aB I a I SAI AS 
A ➔ S I b I ASA I aB Ia I SA I AS
B-+ b B-+ b 
- - . . -- - . -·
4. Converta as regràf remanescentes para a forma apropriada acrescentando
variáveis e regras adicionais. A gramática final em forma normal de Chomsky, a
seguir, é equivalente a G6 • (Na realidade, o procedimento dado no Teorema 2.9
produz diversas variáveis Ui juntamente com várias regras U{ -+ a. Simplifica­
mos a gramática resultante usando uma única variável U e a regra U ➔ a.)
S0 -+ AA1 1 UB Ia ISA IAS 
S-+ AA1 I. UB Ia ISA IAS 
A-+ b I AA1 1 UB Ia ISA IAS 
Ai -+ SA
U-+ a 
B-> b