Forma Normal Greibach
Um CFG está na forma normal de Greibach se as produções estiverem nas seguintes formas -
A → b
A → bD 1 ... D n
S → ε
onde A, D 1 , ...., D n são não terminais eb é um terminal.
Algoritmo para converter um CFG na forma normal de Greibach
Step 1 - Se o símbolo de início S ocorre em algum lado direito, crie um novo símbolo de início S’ e uma nova produção S’ → S.
Step 2- Remova produções nulas. (Usando o algoritmo de remoção de produção nula discutido anteriormente)
Step 3- Remova produções unitárias. (Usando o algoritmo de remoção de produção da unidade discutido anteriormente)
Step 4 - Remova toda a recursão à esquerda direta e indireta.
Step 5 - Faça substituições adequadas de produções para convertê-lo na forma adequada de GNF.
Problema
Converta o seguinte CFG em CNF
S → XY | Xn | p
X → mX | m
Y → Xn | o
Solução
Aqui, Snão aparece no lado direito de nenhuma produção e não há unidades ou produções nulas no conjunto de regras de produção. Portanto, podemos pular da Etapa 1 para a Etapa 3.
Step 4
Agora depois de substituir
X em S → XY | Xo | p
com
mX | m
nós obtemos
S → mXY | mY | mXo | mo | p.
E depois de substituir
X em Y → X n | o
com o lado direito de
X → mX | m
nós obtemos
Y → mXn | mn | o.
Duas novas produções O → o e P → p são adicionadas ao conjunto de produção e, em seguida, chegamos ao GNF final da seguinte forma -
S → mXY | mY | mXC | mC | p
X → mX | m
Y → mXD | mD | o
O → o
P → p