Pesquisa · Mapa mental
Forma normal de Greibach
Uma gramática livre de contexto (GLC) é dita estar na Forma Normal de Greibach (FNG) se todas as suas produções seguem o padrão A → aα, onde 'A' é uma variável não-terminal, 'a' é um símbolo terminal e 'α' é uma sequência (possivelmente vazia) de variáveis não-terminais.
Pontos-chave
- A FNG exige que o lado direito de toda produção comece com um símbolo terminal.
- A transformação para FNG geralmente requer que a gramática esteja inicialmente na Forma Normal de Chomsky (FNC).
- O processo envolve renomear variáveis, reestruturar produções e garantir que terminais iniciem os lados direitos.
- A FNG é útil em algoritmos de reconhecimento de linguagem e análise sintática.
A conversão de uma Gramática Livre de Contexto (GLC) para a Forma Normal de Greibach (FNG) é um processo que exige etapas específicas, sendo o primeiro requisito que a gramática original esteja na Forma Normal de Chomsky (FNC). Após atender a este pré-requisito, o algoritmo prossegue com os seguintes passos:
