GNF significa forma normal de Greibach. Uma CFG (gramática livre de contexto) está em GNF (forma normal de Greibach) se todas as regras de produção satisfizerem uma das seguintes condições:

• Um símbolo inicial gerando ε. Por exemplo, S → ε.
• Um não terminal gerando um terminal. Por exemplo, UMA → uma.
• Um não-terminal gerando um terminal que é seguido por qualquer número de não-terminais. Por exemplo, S → aASB.

Por exemplo:

 G1 = aB, A → aA G2 = S → aAB 

As regras de produção da Gramática G1 satisfazem as regras especificadas para GNF, portanto a gramática G1 está em GNF. No entanto, a regra de produção da Gramática G2 não satisfaz as regras especificadas para GNF, pois A → ε e B → ε contém ε (apenas o símbolo inicial pode gerar ε). Portanto a gramática G2 não está no GNF.

classificação por seleção em java

Passos para converter CFG em GNF

Passo 1: Converta a gramática em CNF.

Se a gramática fornecida não estiver em CNF, converta-a em CNF. Você pode consultar o seguinte tópico para converter o CFG em CNF: Forma normal de Chomsky

Passo 2: Se a gramática existir recursão à esquerda, elimine-a.

Se a gramática livre de contexto contiver recursão à esquerda, elimine-a. Você pode consultar o seguinte tópico para eliminar a recursão à esquerda: Recursão à esquerda

Etapa 3: Na gramática, converta a regra de produção fornecida na forma GNF.

sorriso mais bonito do mundo

Se alguma regra de produção na gramática não estiver na forma GNF, converta-a.

mamãe kulkarni

Exemplo:

 S → XB | AA A → a | SA B → b X → a 

Solução:

Como a gramática G dada já está em CNF e não há recursão à esquerda, podemos pular a etapa 1 e a etapa 2 e ir diretamente para a etapa 3.

A regra de produção A → SA não está no GNF, então substituímos S → XB | AA na regra de produção A → SA como:

 S → XB | AA A → a | XBA | AAA B → b X → a 

A regra de produção S → XB e B → XBA não está no GNF, então substituímos X → a na regra de produção S → XB e B → XBA como:

 S → aB | AA A → a | aBA | AAA B → b X → a 

Agora vamos remover a recursão à esquerda (A → AAA), obtemos:

 S → aB | AA A → aC | aBAC C → AAC | ε B → b X → a 

Agora vamos remover a produção nula C → ε, obtemos:

numerando o alfabeto

 S → aB | AA A → aC | aBAC | a | aBA C → AAC | AA B → b X → a 

A regra de produção S → AA não está no GNF, então substituímos A → aC | aBAC | uma | aBA na regra de produção S → AA como:

 S → aB | aCA | aBACA | aA | aBAA A → aC | aBAC | a | aBA C → AAC C → aCA | aBACA | aA | aBAA B → b X → a 

A regra de produção C → AAC não está no GNF, então substituímos A → aC | aBAC | uma | aBA na regra de produção C → AAC como:

 S → aB | aCA | aBACA | aA | aBAA A → aC | aBAC | a | aBA C → aCAC | aBACAC | aAC | aBAAC C → aCA | aBACA | aA | aBAA B → b X → a 

Portanto, esta é a forma GNF para a gramática G.