Slovník pojmů (ve vývoji)

Formální (generativní) gramatika je $G=(V,T,P,S)$ složena z
\begin{itemize}
 \item konečné množiny \pojem{neterminálů} (variables) $V$
 \item neprázdné konečné množiny \pojem{terminálních symbolů} (\pojem{terminálů}) $T$
 %, např. $\{0,1\} $.
 \item \pojem{počáteční symbol} $S\in V$.
 \item konečné množiny  \pojem{pravidel} (\pojem{produkcí}) $P$ reprezentující rekurzivní definici jazyka. Každé pravidlo má tvar:
 \begin{itemize}
  \item $\alpha A \beta\rightarrow \omega$, $A\in V,\alpha,\beta,\omega\in (V\cup T)^*$
  \begin{itemize}
   \item[] tj. levá strana obsahuje aspoň jeden neterminální symbol.   
  \end{itemize}
   \end{itemize}
\end{itemize}

Říkáme, že gramatika je v \pojem{Greibachové normální formě}, jestliže všechna pravidla mají tvar $A\rightarrow a\beta$, kde $a\in T$, $\beta\in V^*$ (řetězec neterminálů).