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 :

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