Forma normal de Greibach
 | Este artigo não cita fontes confiáveis. (Agosto de 2020) |
Uma gramática livre de contexto está na forma normal de Greibach quando todas as suas produções são da forma:
A → aα
onde A é uma variável, a é um terminal e α é uma palavra de variáveis.
Transformação de uma GLC em uma gramática na FNG[editar | editar código-fonte]
Para que o algoritmo funcione, é necessário que a gramática esteja na Forma Normal de Chomsky. Depois deste requisito satisfeito tem-se os seguintes passos:
1) Renomeação das variáveis em uma ordem crescente qualquer.
2) Transformação de produções para a forma Ar → Asα, onde r ≤ s e exclusão das recursões da forma Ar → Arα.
3) Um terminal no início do lado direito de cada produção.
4) Produções na forma A → aα onde α é composta por variáveis.