epsilon-Nea zu Nea < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Konstruieren sie aus dem angegebenen [mm] $\epsilon$-NEA [/mm] einen NEA.
Bild: http://imageshack.us/photo/my-images/703/unbenanntjfq.jpg/ |
Wir haben folgendes Schema kennengelernt:
1. Prüfe, ob ein akzeptierender Zustand in der ε-Hülle des Startzustandes ist. Falls ja, muss Startzustand des NEA akzeptierend sein.
2. Suche alle Kanten $q [mm] \to [/mm] q′$, bei denen entweder eine [mm] $\epsilon$-Transition [/mm] in q endet, oder aber eine in q′ beginnt
3. Bestimme für jede kritische Kante q [mm] \to [/mm] q′ die predecessor und successor Mengen
4. Füge für jede kritische Kante q [mm] \to [/mm] q′ die Kanten hinzu
5. Lösche die [mm] $\epsilon$-Transitionen.
[/mm]
Ich komm damit leider nicht zurecht. Könnt ihr mir helfen?
Ich hab dann gleich mal mit dem 1. Punkt der Vorgehensbeschreibung ein Problem, da auf dem Bild der erste Zustand kein akzeptierender Zustand ist. Wie geht das dann weiter? Geht's überhaupt weiter? Ich hab keine Ahnung! Was wird eigentlich genau als [mm] $\epsilon$-Hülle [/mm] bezeichnet?
|
|
| |
|
So, ich hab mich jetzt mal weiter damit beschäftigt:
zu 1.) Startzustand des entstehenden NEA's ist akzeptierend.
zu 2.) die kritischen Kanten lauten:
[mm] $q_0 \to q_1$
[/mm]
[mm] $q_1 \to q_4$
[/mm]
Ich denke, dass sollten soweit alle sein. Die [mm] $\epsilon$-Transition [/mm] die auf sich selbst zeigt [mm] ($q_1$) [/mm] darf ich ja nicht mitaufnehmen, oder? Und die Transition zwischen [mm] $q_3$ [/mm] und [mm] $q_4$ [/mm] auch nicht weil es keine reine [mm] $\epsilon$-Transition [/mm] ist, oder?
Könnt ihr mir sagen ob das soweit richtig ist?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:24 Do 12.05.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:24 Do 12.05.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
