Forma normal de Greibach
A Forma Normal de Greibach (FNG) é uma estrutura específica para gramáticas livres de contexto (GLC) onde todas as suas produções seguem um padrão rigoroso. Para que uma GLC esteja na FNG, cada produção deve ter a forma A → aα, onde 'A' é uma variável, 'a' é um terminal, e 'α' é uma sequência (possivelmente vazia) de variáveis. Essa forma é fundamental em diversas aplicações teóricas e práticas da ciência da computação, especialmente na construção de compiladores e na análise sintática.
Pontos-chave
- A FNG é uma forma padronizada para gramáticas livres de contexto.
- Todas as produções na FNG devem ser do tipo A → aα.
- 'A' representa uma variável, 'a' um terminal e 'α' uma sequência de variáveis.
- A transformação para FNG exige que a gramática esteja previamente na Forma Normal de Chomsky (FNC).
Para converter uma Gramática Livre de Contexto (GLC) para a Forma Normal de Greibach (FNG), é essencial que a gramática esteja primeiramente na Forma Normal de Chomsky (FNC). Uma vez que este pré-requisito é atendido, a transformação prossegue através de uma série de passos sistemáticos para garantir que todas as produções se ajustem ao formato A → aα.
