Suche Home Einstellungen Anmelden Hilfe

2.2 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. 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.

____

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: senn • Zuletzt geändert am: