Forma Normal de
Chomsky
Programa de Pós-graduação em Ciência da
Computação - UFU
Profa. Sandra de Amo
Definição
Uma gramática livre do contexto está na Forma Normal de
Chomsky (FNC) se:
 suas regras de produção são do tipo
 A  BC ;
A, B, C são variáveis
 Aa;
A variável e a terminal
 Sϵ

a variável start S não aparece no corpo das regras
Arvores de Derivação de uma FNC




Arvores de derivação são binárias : cada nó
tem no máximo 2 filhos
Nós intermediários são variáveis
Folhas só tem terminais
A variável S só aparece na raiz
Arvores de Derivação
= Start S
= Variáveis distintas de S
= terminais
Toda gramática LC é equivalente a
uma gramática em FNC
Transformação das regras em FNC

Inserir novo simbolo start S0 e regra S0  S
Desta forma, o simbolo start S0 não aparece em nenhum corpo de regra

Remover todas as regras do tipo A  ϵ (inclusive S  ϵ )
Para cada regra onde A tem uma ocorrência do lado direito, inserir uma regra
sem esta ocorrência de A
Exemplo: se R  uAvAw é uma regra então acrescentamos as regras:
R  uvAw
R  uAvw
R  uvw
se R  A é uma regra e R  ϵ não foi removido em um passo precedente então
acrescentamos a regra R  ϵ
Desta forma, obtemos uma gramática sem regras do tipo A  ϵ (para A distinto da
variável start S0 )
Toda gramática LC é equivalente a
uma em FNC

Eliminar regras unitárias do tipo A  B.
Para cada regra começando com B, acrescentar regra análoga, substituindo B por A
na cabeça (a menos que a regra assim obtida seja uma regra unitária já
removida)
Exemplo:

AB
B  C1C2a
B  C1C2a
A  C1C2a
Resolver o problema de regras do tipo X = regras com corpo com
comprimento maior do que 1 e contendo terminais. Para cada terminal a
aparecendo no corpo de uma destas regras de tipo X inserir regra do tipo
Ua a, onde Ua é uma nova variável. Substituir todas as ocorrências de a
em regras do tipo X pela variável Ua.
Exemplo: R  aAB
R UaAB
Ua  a
Toda gramática LC é equivalente a
uma em FNC

Resolver o problema de regras do tipo Y = regras com corpo com
comprimento maior do que 2:
R  ABCD
R  UD
U  ABC
R  UD
U  VC
V  AB
Exemplo
S  ASA | aB
AB|S
Bb|ϵ
S0  S
S  ASA | aB
AB|S
Bb|ϵ
S0  S
S  ASA | aB | a
AB|S|ϵ
Bb
(6 regras)
S0  S
S  ASA | aB | a | AS | SA | S
AB|S
Bb
S0  ASA | aB | a | AS | SA
S  ASA | aB | a | AS | SA
A  B | ASA | aB | a | AS | SA
Bb
S0  ASA | aB | a | AS | SA
S  ASA | aB | a | AS | SA
A  b | ASA | aB | a | AS | SA
Bb
S0  | AA1 | UB | a | AS | SA
S  AA1 | UB | a | AS | SA
A  b | AA1 | UB | a | AS | SA
A1  SA
Ua
Bb
(FNC : 20 regras)