Klassifizierung von Grammatiken

Theorie Icon Bisher haben wir sehr einfache Grammatiken betrachtet, bei denen auf der linken Seite immer nur ein Nichtterminalsymbol stand. Aber auch Regeln der Form
\(\hspace{3cm} aXbSX \rightarrow Saa \)
sind gültige Regeln einer Grammatik.

Die Chomsky-Hierarchie

Theorie Icon Die Chomsky-Hierarchie ist eine Hierarchie von Klassen formaler Grammatiken, die formale Sprachen erzeugen und wurde erstmals 1956 von Noam Chomsky beschrieben. Sie umfasst die Grammatikklassen Typ 0, Typ 1, Typ 2 und Typ 3.

Die von Chomsky definierten Sprachklassen bilden eine Hierarchie. Folgende Teilmengenbeziehung gilt:

\(\mathcal{L}_\text{Typ_3} \subset \mathcal{L}_\text{Typ_2} \subset \mathcal{L}_\text{Typ_1} \subset \mathcal{L}_\text{Typ_0} \)

Die folgende Abbildung veranschaulicht die Teilmengenbeziehung:

Chomsky Hierarchie

Jede reguläre Grammatik ist automatisch auch eine kontextfreie Grammatik. Die Klasse der regulären Sprachen ist eine echte Teilmenge der Menge der kontextfreien Sprachen.

Die Hierarchiestufen unterscheiden sich darin, wie rigide die Einschränkungen für die Form zulässiger Produktionsregeln auf der jeweiligen Stufe sind, bei Typ-0-Grammatiken sind sie uneingeschränkt, bei höheren Stufen fortschreitend stärker beschränkt.

Beispiele

Im folgenden sind Beispiele für Grammatiken der unterschiedlichen Klassen aufgelistet:

Die Grammatik \(G = ({B,C,S},{a,b,c},P,S)\) hat die folgenden Produktionsregeln \(P\):
\(S \rightarrow aSBC | aBC\)
\(CB \rightarrow BC\)
\(aB \rightarrow ab\)
\(bB \rightarrow bb\)
\(bC \rightarrow bc\)
\(cC \rightarrow cc\)

Die zugehörige Sprache ist \(L(G)={a^nb^nc^n | n \in \mathbb{N}, n \ge 1}\)

Kontextfreie Grammatiken

Das Hauptaugenmerk liegt in der Unterscheidung zwischen kontextsensitiv und kontextfrei. Kontextfreiheit bedeutet, dass man ein Nichtterminal \(X\) durch ein Wort \(a\) unabhängig davon ersetzen kann, wo sich das \(X\) in dem bisher abgeleiteten Wort befindet und welche Symbole seine Nachbarn sind.

Im Gegensatz dazu hängt bei kontextsensitiven Regeln das Ersetzen eines Nichtterminals von seiner Umgebung ab.

Übung