Chomsky Hierarchie und Epsilon
Frank Radmacher
> Hallo Newsgroup :-)!
Hallo auch,
also erstmal sei gewarnt, dass sich alles was ich schreibe auf die
Vorlesung von Prof. Indermark bezieht. Angeblich gibts ja in der
gängigen Literatur durchaus kleinere Abeweichungen in der Definition der
Normalformen von der Indermark-Vorlesung.
Aber ich denke, Du lernst für die letzte Indermark-Klausur, richtig?
Alles was ich Dir jetzt sage findest Du übrigens in schön lesbarer Form
im Sadip-Skript (3.Auflage) auf Seite 26.
> Wenn ich die Chomsky-Hierarchie recht verstehe, "geht" sie so, wobei jeder
> Grammatiktyp die Voraussetzungen aller vorherigen Grammatiktypen erbt:
>
> Typ 0: Alles was ausschaut wie ne Grammatik.
Genau, eine eine beliebige Chomsky-Grammatik. Beachte also nur die
Definition von Chomsky-Grammatik.
> Typ 1: |Linke Produktionsseite| <= |Rechte Produktionsseite|
Das halte ich für Blödsinn (bzw. für zu allgemein).
Typ 1 heißt, Regeln haben die Form
S -> epsilon _oder_
gamma A delta -> gamma beta delta (mit beta nicht gleich epsilon)
Wenn weiterhin Regel S->epsilon existiert, darf S auf keiner rechten
Regelseite vorkommen.
Man sollte für die Klausur hier schon die Definition können. Wie willst
Du sonst Begründen, dass eine Gramatik (nicht) vom Typ 1 ist?
> Typ 2: Linke Produktionsseite = Genau ein Nichtterminal
richtig.
> Typ 3: Rechte Produktionsseite =
> i) Genau ein Terminal
> ii) Ein Terminal mit Nichtterminal rechts (links) daneben
> => entweder rechts- oder linkslinear!
Auch richtig, wobei Du beachten musst, dass eine Grammatik nur
linkslineare exklusiv-oder rechtslineare Regeln enthalten darf. Hat man
eine Grammatik, in der beide rechts- und linkslineare Regeln zusammen
auftauchen ist sie nicht mehr vom Typ 3.
> 1.: Ist das obige korrekt?
Größtenteils, ich würde mir aber an Deiner Stelle angewöhnen näher an
den Definitionen zu arbeiten.
> 2.: Aber was ist mit Produktionen, die auf epsilon zeigen? Sowas hier:
>
> S -> epsilon
> A -> epsilon...
>
> Die Länge von epsilon ist ja Null, also müßten das ja alles
> Typ0-Grammatiken
> sein. Oder gibt es da eine Ausnahmeregel?
Nein, auch andere Grammatiken dürfen Regeln mit epsilons enthalten, z.B.
darf bei einer Typ3-Grammatik in der Definition das w durchaus gleich
epsilon sein.
Wie gesagt, arbeite näher an den Definitionen!
> 3.: Kann eine Grammatik durch Umformung ihren Typ ändern? (Meine Meinung: JA,
> siehe z.B. Normierung).
Genau. Was sich durch Normierung nicht ändern kann ist der Typ der Sprache.
Weiterhin solltest Du beachten, dass die Chomski-Hirachie nur bzgl. der
Typen der Sprachen eine Hirachie darstellt, nicht aber bzgl. der
Grammatiken.
So kann es z.B. sein, dass eine Grammatik von Typen 0,2 und 3 ist, nicht
aber von Typ 1. (Darauf bin ich in der Klausur damals reingefallen ;-))
> Dank Euch!! Axel
Gern geschehen,
Frank
--
Geist ziert Leben, Mut hegt Siege, Beileid trägt belegbare Reue,
Neid dient nie, nun eint Neid die Neuerer, abgelebt gärt die Liebe,
Geist geht, umnebelt reizt Sieg.
Frank Radmacher
>>>Typ 1: |Linke Produktionsseite| <= |Rechte Produktionsseite|
>>
>>Das halte ich für Blödsinn (bzw. für zu allgemein).
>
> Hmm, das stammt exakt so aus Uwe Schöning, Theoretische Informatik -
> kurzgefaßt, ein Buch, das Indermark ja auch empfiehlt, oder? Ich fand die
> Definition da etwas eingängiger.
Hmm, ist ja interessant. Nun, ich habe leider noch keine Bücher zu
diesem Thema gelesen, kann mich aber daran erinnern, dass Prof.
Indermark in der Vorlesung vor dieser Abweichung gewarnt hat (ansonsten
empfiehlt er sogar ausdrücklich alle Bücher von Schöning, auch zu
anderen Themen :-)).
>>Typ 1 heißt, Regeln haben die Form
>>S -> epsilon _oder_
>>gamma A delta -> gamma beta delta (mit beta nicht gleich epsilon)
>
> Sorry, das kapier ich einfach nicht. Kannst Du das näher erläutern? Wer sind
> gamma, delta, beta? Inwiefern weicht die Definition von meiner ab?
Schau erstmal ins Sandip-Skrip (3.Aufl.) auf Seite 26. Als ASCII-Text
kann man die Definition eh nicht vernünftig lesen.
http://www.saw.rwth-aachen.de/~sandip/showpage.php?page=downloads&lang=de
Dann betrachte z.B. die Grammatik mit Startsymbol S und Produktion
S -> epsilon.
Nach Deiner Definition nicht von Typ 1, nach Indermark schon. Prof.
Indermark erlaubt (unter bestimmten Bedingungen) die epsilon-Regelch in
Typ1-Grammatiken.
>>So kann es z.B. sein, dass eine Grammatik von Typen 0,2 und 3 ist, nicht
>>aber von Typ 1. (Darauf bin ich in der Klausur damals reingefallen ;-))
>
> Neee, echt? Hast Du da ein Beispiel, das wußte ich noch gar nicht!
Klar,die Grammatik mit Startsymbol S und Produktion:
S -> A,
A -> epsilon.
Die Grammatik ist vom Typ 0,2 und 3 nicht aber vom Typ 1.
> Vor allem:
> Schöning baut das ja aufeinander auf: Eine Typ X Grammatik ist vom Typ Y (hier
> Y = X+1), falls ...
> Eigentlich impliziert das doch die Hierarchie, oder?
Komisch, mit Deiner Schöning-Definition kommt das aber auch nicht hin.
Hast Du mir vielleicht einen Teil der Definition verschiegen? ;-)
Hab leider keinen Schöning hier... werde aber nachher zumindest mal Googeln.
> Inwiefern können sich Indermark und Schöning da eigentlich definitionsmäßig was
> tun? Schließlich ists ja nicht deren Definition sondern die von Chomsky, oder?
Also definieren kann man sich ja was man will. Ob Prof. Indermark es
auch Chomsky-Hirachie nennen sollte, ist die Frage. Fakt ist, er hats
getan. ;-)
Ich weiß aber auch nicht, wie die Originaldefinition vom Herrn Chomsky
lautet, tippe aber auch eher auf die Schöning-Definition (vielleicht ist
diese ja doch eine richtige Hirachie).
Für die Klausur solltest Du Dich zumindest wohl oder übel mit Indermarks
Definition abfinden.
Gruß,
Frank Radmacher
Im Internet findet man viele leicht amders formulierte Definitionen.
Weit verbreitet ist diese:
http://de.wikipedia.org/wiki/Chomsky-Hierarchie
Diese erlaubt (wie die meisten, die ich finde) auch das Erzeugen vom
leeren Wort. Es könnte also auch sehr wohl sein, dass der Herr Schöning
ein Allgeingang mit seiner Definition gemacht hat.
Einen Hinweis, dass die Grammatiken eine Hierarchie bilden finde ich
allerdings nirgenswo. Alle Quellen sprechen ausschließlich von einer
Hierarchie der Sprachklassen.
Viel Spaß noch beim lernen,
Frank, der jetzt auch "Hierarchie" richtig schreibt ;-)