Formale Grammatik: Chomsky-Hierarchie

Was eine formale Grammatik ist, habe ich bereits in vorherigen Artikeln beschrieben. Wer also nochmal schnell nachlesen möchte kann das hier tun, denn darauf bauen wir heute auf. In dem nachfolgendem Artikel geht es um die sogenannte Chomsky-Hierarchie. Die Chomsky-Hierarchie beruht auf dem Linguisten Noam Chomsky, der 1956 erstmal formale Grammatiken entsprechend der Bildung ihrer Produktionsregeln klassifiziert hat. Er hat also definiert, nach welchen Einschränkungen bzw. Regeln einer formalen Grammatik eine formale Sprache erzeugen kann.

Typ 0 unbeschränkte Grammatik (uG)

Dieser Typ ist der leicht verständlichste, denn er besitzt einfach keinerlei Einschränkungen. Mehr gibt es zum Typ 0 auch gar nicht zu sagen

Typ 1 kontextsensitive Grammatik (ksG)

Bei Typ 1 der Chomsky-Hierarchie sieht es schon anders aus. Es gilt zwar prinzipiell die Gestaltung der Regeln gemäß Typ 0. Allerdings kommen hierbei noch die längenmonotone Regeln hinzu. Das bedeutet nichts anderes, als:

α → β

|α| ≤ |β|

Heißt also, die Länge von a muss kleiner gleich der Länge von b sein. Die rechte Seite des Regelwerks muss also länger oder gleich der linken Seite sein. Die einzige Ausnahme bildet hier s → ∈. Anders ausgedrückt, ich darf das Start- oder Spitzensymbol auf das leere Wort ∈ ableiten. Diese Ableitung ist möglich, sofern s in keiner Regel auf der rechten Seite auftaucht.

Typ 2 kontextfreie Grammatik (kfG)

Grundsätzlich gilt hier das Regelwerk von Typ 1 mit dem Unterschied, dass α ∈ N (Nichtterminale) ist. Außerdem ist im Typ 2 eine Ableitung von α auf das leere Wort ε möglich, sprich α → ε.

Typ 3 reguläre Grammatik (rG)

Auch hier gilt wieder grundlegend das Regelwerk von Typ 2. Bei der regulären Grammatik gibt es entweder nur linkslineare, also α → Ax, oder nur rechtslineare, also α → xA, Regeln, mit x ∈ T (Terminale) und A ∈ N (Nichtterminale). Linkslinear bezeichnet den Umstand, dass immer das am weitesten links stehende Nichtterminal durch die Produktionsregeln ersetzt wird. Rechtslinear entsprechend umgekehrt, also das am weitesten rechts stehende Nichtterminal.