Forma normal de Greibach

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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.