Suche Home Einstellungen Anmelden Hilfe  

2.2 Chomskyhierarchie

Grammatik G = (N, T, P, S)

Typbeziehungen in der Chomskyhierarchie
Es gibt Typ-0-Sprachen, die keine Typ-1-Sprachen sind, für die es also keine kontextsensitive Grammatik gibt. Umgekehrt gilt jedoch, eine reguläre Sprache ist auch eine kontextfreie Sprache usw.

Das allgemeine Regelformat der Art x->y, wobei x und y beliebige Zeichenketten über Terminal- und Nichtterminalalphabet sind, kann beschränkt werden. Aber nicht jede Sprache kann auch durch ein beschränkteres Regelformat dargestellt werden. Man unterscheidet verschiedene Sprachklassen, je nachdem, welchen Beschränkungen die Regeln unterliegen.
Die Grammatiken und Sprachen der Chomskyhierarchie werden hier näher vorgestellt.

Chomskyhierarchie

Die Regelformate bilden eine Hierarchie: Jede Regel eines höheren (beschränkteren) Typs ist ein Spezialfall des Regelformats eines niedrigeren (unbeschränkteren) Typs. Man spricht z.B. von kontextfreier Sprache, wenn diese Sprache durch eine kontextfreie Grammatik dargestellt werden kann.

____

Bezeichnerdefinition

Man erkennt, die linke Regelseite besteht aus mindestens einem Nichtterminal und einer beliebigen (auch leeren) Kombination weiterer Terminale und Nichtterminale. Im Fall von kontextfreien und regulären Grammatiken besteht die linke Regelseite aus genau einem Nichtterminal.

Zu kontextsensitiven Grammatiken gibt es eine alternative Schreibweise, die zu obigen Regelbeschränkung äquivalent ist.

Einführung 1   2   3   4 Von der Grammatik zur Sprache (1)

Benutzer: Gast • Besitzer: matthias • Zuletzt geändert am: