Die vier von Chomsky beschriebenen Grammatiktypen entstehen ausgehend von einer nicht eingeschränkten Grundgrammatik (der Typ-0-Grammatik) dergestalt, dass zunehmend Einschränkungen bezüglich der für den Typ erlaubten Produktionsregeln gemacht werden.

Rekursiv aufzählbare Sprachen bilden die oberste Stufe der Chomsky-Hierarchie und heißen deshalb auch Typ-0-Sprachen (oder Grammatiken). Sie können somit auch als all die Sprachen definiert werden, deren Wörter sich durch eine beliebige formale Grammatik ableiten lassen.

Eine formale Grammatik G ist kontextsensitiv (Typ-1), wenn für jede Produktionsregel [mm] w_1 \rightarrow w_2 [/mm]  gilt: [mm] \left| w_1 \right| \le \left| w_2 \right|. [/mm] Weniger formal bedeutet das: alle rechten Regelseiten sind nicht kürzer als die zugehörigen linken Regelseiten.

Man schreibt G [mm] \in \mbox{Typ}_1. [/mm]

Im Gegensatz zu kontextfreien Grammatiken kann die Anzahl der Symbole auf der linken Regelseite auch größer als 1 sein.

Typ-1-Grammatiken besitzen Regeln der Form [mm] \alpha [/mm] A [mm] \beta \rightarrow \alpha [/mm] x [mm] \beta, [/mm] wobei A ein Nichtterminal und α,β,x Wörter bestehend aus Terminalen (Σ) und Nichtterminalen (N) sind. Die Wörter α und β können leer sein, aber x muss mindestens ein Symbol (also ein Terminal oder ein Nichtterminal) enthalten.

An diesem Beispiel kann auch die Bezeichnung kontextsensitiv erklärt werden. Durch Regeln der Form [mm] \alpha [/mm] A [mm] \beta \rightarrow \alpha [/mm] x [mm] \beta [/mm] ist es möglich die Variable A durch x zu ersetzen aber nur dann, wenn A in einem bestimmten Kontext also hier zwischen α und β steht.

Einzige Ausnahme zu obiger Form bildet die Regel S [mm] \rightarrow \varepsilon, [/mm] die eventuell benötigt wird, das leere Wort [mm] \varepsilon [/mm] abzuleiten. Sie darf aber nur dann verwendet werden, wenn das Startsymbol S auf keiner rechten Regelseite vorkommt.

Eine kontextfreie Grammatik G ist eine kontextsensitive Grammatik, deren Produktionsregeln soweit eingeschränkt sind, dass immer genau ein Nichtterminal durch eine evtl. auch leere Folge von Zeichen (Nichtterminale oder Terminale) ersetzt wird. Mathematisch wird dies durch [mm] \forall (w_1 \rightarrow w_2) \in [/mm] P : ( [mm] w_1 \in [/mm] N) [mm] \wedge \left(w_2 \in (N \cup T)^\star\right) [/mm] beschrieben.

Man schreibt G [mm] \in \mbox{Typ}_2. [/mm]

Typ-2-Grammatiken besitzen nur Regeln der Form A [mm] \rightarrow \gamma, [/mm] wobei A ein Nichtterminal und γ ein Wort bestehend aus Terminalen und Nichtterminalen ist. (Um das leere Wort [mm] \varepsilon [/mm] zu erzeugen, darf hier für γ auch [mm] \varepsilon [/mm] verwendet werden.)

G = [mm] \left(N,\Sigma,P,S\right) [/mm] ist eine kontextfreie Grammatik, deren Produktionsregeln weiter eingeschränkt sind. Es gibt rechtsreguläre als auch linksreguläre Grammatiken, wobei normalerweise mit regulär die rechtsregulären Grammatiken gemeint sind.

Die rechte Seite einer Produktion [mm] w_2 [/mm] darf für rechtsreguläre Sprachen nur ein Terminalsymbol oder ein Terminal gefolgt von einem Nichtterminal sein. D.h. ein Wort einer solchen regulären Sprache entsteht durch Anfügen von Terminalsymbolen auf der rechten Seite. Entsprechend gilt für linksreguläre Sprachen, dass die rechte Seite [mm] w_2 [/mm] nur ein Terminal oder ein Nichtterminal gefolgt von einem Terminal sein darf..

Für die Produktionen P einer rechtsregulären Grammatik G [mm] \in \mbox{Typ}_3 [/mm] gilt :
[mm] \forall (w_1 \rightarrow w_2) \in [/mm] P : [mm] (w_1 \in [/mm] N) [mm] \wedge (w_2 \in \Sigma \cup \Sigma [/mm] N)

Gültige Produktionen einer regulären Grammatik wären beispielsweise:

    [mm] \begin{matrix} A \rightarrow & aA & \quad \mathrm{(f\ddot{u}r \ rechtsregul\ddot{a}r)} \\ A \rightarrow & Aa & \quad \mathrm{(f\ddot{u}r \ linksregul\ddot{a}r)} \\ A \rightarrow & a & \quad A \in N, a \in \Sigma \end{matrix} [/mm]