Grammatiken (2)
Wenn wir auch ein Erzeugungsverfahren besitzen,
das die zur Sprache L(G) gehörenden Wörter systematisch
alle aufzählt, so sind wir doch meist auch an
einem Entscheidungsverfahren interessiert, das
für ein vorgelegtes Wort w 
T* feststellt, ob es in L(G) liegt.
Leider braucht es das allgemein nicht zu geben.
Daher teilt man die Grammatiken (und die zugeordneten Sprachen)
in Klassen ein danach, ob es ein Entscheidungsverfahren gibt,
und womöglich gar ein effizientes. Die Klassifikation richtet
sich nach der Gestalt der Regeln 
:
-
Klasse 0: keine Einschränkung.
Hier muß kein Entscheidungsverfahren existieren.
-
Klasse 1 (kontextsensitive Grammatiken):
|| <= ||;
also darf die linke Seite einer Regel nicht länger
als die rechte Seite sein.
Hier gibt es ein Entscheidungsverfahren, aber seine Kosten sind
astronomisch hoch.
-
Klasse 2 (kontextfreie Grammatiken):
N;
die linke Seite ist ein einziges
Nichtterminalsymbol, das bei einem Ableitungsschritt unabhängig
von seiner Umgebung ersetzt wird, daher der Name kontextfrei.
Die Kosten des Entscheidungsverfahrens wachsen für Wörter der
Länge n höchstens wie n**3 an, in günstigeren Fällen
gar nur proportional zu n. Dies ist in der Praxis brauchbar; hierher
gehören die meisten Programmiersprachen.
-
Klasse 3 (reguläre Grammatiken):
zusätzlich T oder auch TN;
das Entscheidungsverfahren macht für ein Wort der Länge n
nur n Schritte!
In allen Fällen erlauben wir als Ausnahme die Regel
S 
,
falls S auf keiner rechten Seite vorkommt.
Das macht einige Sätze einfacher, etwa den folgenden:
Für die Mengen der zugehörigen Sprachen gilt:
Klasse 3 
Klasse 2 Klasse 1 Klasse 0
Hier haben wir ausgenutzt, daß man die Sprachen auch
in Klassen einteilen kann nach der höchsten Nummer einer Klasse,
in der es zu der Sprache eine Grammatik gibt
(es gibt zu einer Sprache immer viele Grammatiken,
deren Äquivalenz man nicht immer leicht sieht).
zurück |
Inhalt | Index |
vor |
Vorlesung
Klaus Lagally, 22. Februar 2000, 19:36