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.