Verständnis: Chomsky-Hierarchie

[fkerber]

Hi!

Ich hätte eine Frage bzgl. der Chomsky-Hierarchie. Ich habe zwar auch den Wikipedia-Artikel gelesen, aber verstanden nicht wirklich... ( http://de.wikipedia.org/wiki/Chomsky-Hierarchie )

Könnte mir das in leicht verständlichen Worten darlegen?
Ich weiß nur, dass es um die Einteilung von Grammatiken geht, aber sonst?


Ciao Frederic

[Gausi]

Eine Grammatik in diesem Sinne ist ja ein 4-Tupel. Man hat ein Alphabet Sigma (z.B. abcdef..z), eine Menge N von weiteren Symbolen, eine Menge von Produktionsregeln P sowie ein Startsymbol S aus N.

Die Produktionsregeln geben an, wie man aus dem Startsymbol S ein Wort aus der Sprache erhält, was durch diese Gramatik gegeben ist.

Beispiel:
Sigma = abcde...z
N = {#}
S = #
P = { # -> o#o oder # -> tt}

Die Sprache, die diese Grammatik erzeugt enthält die Wörter otto, oottoo, ooottooo, usw.

Es sollte klar sein, dass im Wesentlichen die Produktionsregeln dafür verantwortlich sind, wie die Sprache am Ende aussieht. Ebenso sollte klar sein, dass man nicht alle Sprachen erzeugen kann, wenn man bei den Produktionsregeln gewisse Einschränkungen macht. Und genau das beschreibt die Chomsky-Hierarchie.

Bei Sprachen vom Typ 0 gibt es keine Einschränkungen der Regelmenge.

Bei Sprachen vom Typ 1 (kontextsensitiv) muss die rechte Seite der Regel mindestens genauso lang wie die linke sein. Eine Regel der Form ot#to -> oto wäre also nicht erlaubt. Was aber erlaubt ist, dass die linke Seite aus mehreren Symbolen besteht. Daher "kontextsensitiv". Erlaubt ist oftmals nur S -> eps, wobei eps das leere Wort ist (falls das zur Sprache dazugehören soll).

Bei Sprachen von Typ 2 (kontextfrei) muss die linke Seite aus genau einem Symbol bestehen. Eine Regel wie AB -> CD ist dann nicht erlaubt.

Bei Typ 3 (regulär) hat jede Regel die Form A -> aB, wobei A, B aus N sind, und a aus Sigma. Es ist dann z.B # -> o#o nicht erlaubt.

Für jede Art der Sprache gibt es eine bestimmte Art von "Maschine" oder "Automat" die diese Sprache akzeptiert/entscheidet. Das Beispiel von oben ist eine Sprache vom Typ 2 (kontextfrei). Es lässt sich leicht so erweitern, dass alle Palindrome (otto, anna, uhu, ..) dazu gehören, und sonst nichts. Man kann z.B. zeigen, dass die Menge aller Palindrome nicht durch eine reguläre Grammatik angegeben werden kann (und noch eine Menge weiteren Zeugs ;-))