Grammatiken

$ G\ =(V\ ,\Sigma ,P\ ,S\ ) $

$ V\ $ endliche Menge der Variablen, nicht terminal Symbole
$ \Sigma \ $ endliche Menge von terminal Symbolen, Alphabet
$ P\ $ Regeln
$ S\ $ Startsymbol , $ S\ $

Je nach Spracheklasse unterliegen Grammtikregeln einer gewissen Form.

$ REG\subset DCFL\subseteq CFL\subseteq CSL\subseteq RE $

$ REG $
$ REG $
$ REG $
$ RE $ rekursive aufzählbare Sprache