Indietro

ⓘ 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 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 → α A 1 A 2 ⋯ A n {\displaystyle A\to \alpha A_{1}A_{2}\cdots A_{n}}

oppure

S → ε {\displaystyle S\to \varepsilon }

dove A è un simbolo nonterminale, α è un simbolo terminale, A 1, A 2, …, A n {\displaystyle A_{1},A_{2},\ldots,A_{n}} è una sequenza di simboli nonterminali eventualmente vuota che non include come simbolo iniziale lassioma, S è lassioma, 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 è nellordine di al più On 4, dove n è la dimensione della grammatica originale. 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.

                                     

1. Riferimenti

  • 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