title: Forma normale di Greibach
text: # 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.
  
  