Klassifizierung von Grammatiken

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

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:

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}\)

Die Grammatik, die im interaktiven Element Linksableitung gegeben ist, ist eine kontextfreie Grammatik. Sie lautet:

\(G = ({B,C,S},{a,b,c},P,S)\) mit \(P\):
\(S \rightarrow dS\)
\(S \rightarrow A\)
\(A \rightarrow aA\)
\(A \rightarrow aB\)
\(A \rightarrow a\)
\(B \rightarrow bBA\)

Wir können keinen regulären Ausdruck zu dieser Sprache angeben, weil es sich nicht um eine reguläre Sprache handelt. In den Produktionsregeln von regulären Sprachen darf nur ein Nichtterminalsymbol stehen, das ist mit

\(B \rightarrow bBA\)

nicht gegeben.

Die folgende Grammatik ist eine reguläre Grammatik:

\(G = \{S,X\},\{a,b\}, \{S \rightarrow abX, X \rightarrow bX, X \rightarrow aa\}\)

Zu dieser Grammatik können wir einen regulären Ausdruck angeben, der dieselbe Sprache beschreibt. Er lautet: \(a{b^{+}}aa\)

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.

Klassifizierung von Grammatiken

Die Chomsky-Hierarchie

Beispiele

Kontextfreie Grammatiken

Übung