Suche Home Einstellungen Anmelden Hilfe  

4.3.1 EA und RG

Indirekt über Reguläre Ausdrücke

Für jeden RA r ist ein NEA M konstruierbar mit L(r)=L(M).

Induktionsanfang:

rM
epsilonEin Zustand q, der zugleich Start- und Endzustand ist.
ØZwischen Start- und Endzustand gibt es keinen Übergang.
aZwischen Start- und Endzustand gibt es einen Übergang, bei dem das Symbol a konsumiert wird.

Induktionsschritt: Wenn r und s RA mit den Automaten M1 und M2 sind, dann

Vereinigunge-Übergänge von neuem Startzustand zu Startzuständen von M1 und M2; das gleiche für Endzustände
KonkatenationStartzustand M1; e-Übergang von Endzustand von M1 zum Startzustand von M2
Sterne-Übergänge von End- zum Startzustand; zusätzlicher Start- und Endzustand zur Generierung von e

1   2   Äquivalenz von EA und rechtslinearen Grammatiken

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