Suche Home Einstellungen Anmelden Hilfe  

4.3.1 Äquivalenz von EA und rechtslinearen Grammatiken

Direkte Umwandlung

Umwandlung G in EA Beispiel Nomenkomplex

Umwandlung EA in G Beispiel Datum

Von der Grammatik zum EA

Vorgehen:
  • Jedes Nichtterminal wird zu einem Zustand.
  • Ein zusätzlicher Zustand wird eingeführt - der Endzustand QF
  • Für jede Regel der Form A -> a B gibt es einen Übergang B Element delta(A, a)
  • Für jede Regel der Form A -> a gibt es einen Übergang QF Element delta(A, a)
  • Sigma enthält die Elemente von T
Das Ergebnis ist ein nicht-deterministischer endlicher Automat.

Vom EA zur Grammatik

Vorgehen:
  • Jeder Zustand wird zu einem Nichtterminal
  • Für jeden Übergang delta(q, a) = p gibt es eine Regel [q] -> a[p]
  • Besonders beachtet werden müssen dabei Endzustände: Ist p ein Enzustand, so muss es zusätzlich die Regel [q] -> a geben.

EA und RG 1   2   Übersicht: Sprachklassen

Benutzer: Gast • Besitzer: senn • Zuletzt geändert am: