Forma normale di Greibach

In informatica e nella teoria dei linguaggi formali, una grammatica libera dal contesto è nella forma normale di Greibach (detta anche GNF, dall'inglese Greibach normal form) 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