Grammatiken

<math> G\ = ( V\ , \Sigma , P\ , S\ ) </math>

<math>V\ </math> endliche Menge der Variablen, nicht terminal Symbole
<math>\Sigma\ </math> endliche Menge von terminal Symbolen, Alphabet
<math>P\ </math> Regeln
<math>S\ </math> Startsymbol , <math>S\ </math>

Je nach Spracheklasse unterliegen Grammtikregeln einer gewissen Form.

<math> REG \subset DCFL \subseteq CFL \subseteq CSL \subseteq RE </math>

<math> REG\ </math>
<math> CFL\ </math>
<math> CSL\ </math>
<math> RE\ </math> rekursive aufzählbare Sprache