Forma normale di Greibach

In informatica e nella teoria dei linguaggi formali, una grammatica libera dal contesto è nella Forma normale di Greibach se la parte destra di tutte le produzioni inizia con un simbolo terminale, eventualmente seguito da alcune variabili. Unica eccezione ammessa è la presenza della stringa vuota (epsilon, ε) come appartenente al linguaggio descritto. La forma normale prende il suo nome da Sheila Greibach.

Più precisamente, una grammatica context-free è nella forma normale di Greibach, se tutte le regole di produzione sono nella forma:

$A\to \alpha A_{1}A_{2}\cdots A_{n}$

oppure

$S\to \varepsilon$

dove A è un simbolo nonterminale, α è un simbolo terminale, $A_{1},A_{2},\ldots ,A_{n}$ è una sequenza di simboli nonterminali (eventualmente vuota) che non include come simbolo iniziale l'assioma, S è l'assioma, e ε è la stringa vuota.

Si noti che la grammatica non presenta ricorsioni sinistre.

Ogni grammatica context-free può essere trasformata in una grammatica equivalente posta in forma normale di Greibach. (Alcune definizioni non ammettono la definizione della seconda regola, nel qual caso una grammatica context-free che genera la stringa nulla non può essere trasformata.) In particolare, esiste una costruzione che assicura che la forma normale della grammatica risultante è nell'ordine di al più O(n⁴), dove n è la dimensione della grammatica originale. Tale conversione può essere usata per provare che ogni linguaggio context-free può essere accettato da un automa non-deterministico di tipo automa a pila.

Data una grammatica in GNF e una stringa di lunghezza n derivabile dalla grammatica , ogni top-down parser si fermerà a profondità n.

Bibliografia

• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. (See chapter 4.)
• Norbert Blum and Robert Koch: Greibach Normal Form Transformation Revisited. Information and Computation 150(1), 1999, pp. 112–118 preprint

Voci correlate

• Forma di Backus-Naur
• Forma normale di Chomsky
• Forma normale di Kuroda