Forma normale di Greibach

Da Wikipedia, l'enciclopedia libera.

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 ε e la stringa vuota.

Si noti che la grammatica non deve presentare 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(n4), dove n è la dimensione della grammatica originale.[1] Tale conversione può essere usata per provare che ogni linguaggio context-free può essere accettato da una 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.

Voci correlate[modifica | modifica sorgente]

Note[modifica | modifica sorgente]

  1. ^ Blum and Koch (1999)

Riferimenti[modifica | modifica sorgente]

  • 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