Forma normale di Greibach
# 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^4),$ 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.

