Umwandlung von NFA in DFA < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo,
Ich lese momentan im Buch "Theoretische Informatik kurzgefasst" wie man einen NFA in einen DFA umwandeln kann.
Es ist dort wiefolgt erklärt:
Gegeben ist ein NFA:
1.) Die neuen Zustände des DFA sind die Potenzmenge der alten Zustände
2.) Startzustand des DFA ist der neue Zustand, der die Vereinigung der alten Startzustände ist.
3.) Eingabealphabet bleint natürlich gleich
4.) Endzustände: Die neuen Endzustände sind alle neuen Zustände, die einen alten Endzustand enthalten.
Das ist soweit alles klar. Was mir jetzt aber noch fehlt ist wie die neuen Zustandsübergänge zustande kommen!
Laut Buch, Vorlesung und Internet geht es so:
[mm] \delta'(Z', [/mm] a) = [mm] \bigcup_{z\ in Z'} [/mm] = [mm] \delta''(Z', [/mm] a), Z' [mm] \in [/mm] Z
Kann mir bitte jemand erklären wie man nun vorgeht?
Ich habe hier eine beispielaufgabenstellung, falls ihr diese braucht um euch hineinversetzen könnt.
Ich habe einen NFA, der folgende Zustände hat:
Z0, Z1, Z2
Die Übergänge sind:
[mm] \delta(Z0, [/mm] 0) = Z0
[mm] \delta(Z0, [/mm] 1) = Z0
[mm] \delta(Z0, [/mm] 0) = Z1
[mm] \delta(Z1, [/mm] 0) = Z2
Die neuen Zustände sind klar:
Z' = [mm] \mathcal{P}(Z) [/mm] = {Z0, Z1, Z2, Z0Z1, Z0Z2, Z1Z2, Z0Z1Z2, [mm] \emptyset}
[/mm]
Doch: Wie komm ich jetzt darauf wie diese vielen neuen Zustände korrekt verknüpft werden müssen?
Ich verstehe die obige mathematische Notation darüber wie [mm] \delta' [/mm] zustande kommen soll nicht. Aber kann es sein, dass ich die neuen Zustandsübergänge selbst finden muss?
Vielen Dank.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:11 Fr 11.09.2009 | | Autor: | felixf |
Hallo!
> Ich lese momentan im Buch "Theoretische Informatik
> kurzgefasst" wie man einen NFA in einen DFA umwandeln
> kann.
>
> Es ist dort wiefolgt erklärt:
>
> Gegeben ist ein NFA:
>
> 1.) Die neuen Zustände des DFA sind die Potenzmenge der
> alten Zustände
> 2.) Startzustand des DFA ist der neue Zustand, der die
> Vereinigung der alten Startzustände ist.
Du meinst: die Menge, die genau alle Startzustaende enthaelt.
> 3.) Eingabealphabet bleint natürlich gleich
> 4.) Endzustände: Die neuen Endzustände sind alle neuen
> Zustände, die einen alten Endzustand enthalten.
Genau. Der Zustand des DFAs sagt sozusagen, welche Zustaende der NFA in genau diesem Mment alle annehmen koennte.
> Das ist soweit alles klar. Was mir jetzt aber noch fehlt
> ist wie die neuen Zustandsübergänge zustande kommen!
>
> Laut Buch, Vorlesung und Internet geht es so:
>
> [mm]\delta'(Z',[/mm] a) = [mm]\bigcup_{z\in Z'}[/mm] = [mm]\delta''(Z',[/mm] a), Z'
> [mm]\in[/mm] Z
Das zweite Gleichheitszeichen soll da weg, oder? Und [mm] $\delta'' [/mm] = [mm] \delta$? [/mm] Und $Z$ ist die Potenzmenge der Zustaende des NFAs?
> Kann mir bitte jemand erklären wie man nun vorgeht?
Nun, genau so wie das da steht.
> Ich habe hier eine beispielaufgabenstellung, falls ihr
> diese braucht um euch hineinversetzen könnt.
>
> Ich habe einen NFA, der folgende Zustände hat:
>
> Z0, Z1, Z2
>
> Die Übergänge sind:
>
> [mm]\delta(Z0,[/mm] 0) = Z0
> [mm]\delta(Z0,[/mm] 1) = Z0
> [mm]\delta(Z0,[/mm] 0) = Z1
> [mm]\delta(Z1,[/mm] 0) = Z2
Du meinst eher
> [mm]\delta(Z0, 0) = \{ Z0 \}[/mm]
> [mm]\delta(Z0, 1) = \{ Z0 \}[/mm]
> [mm]\delta(Z0, 0) = \{Z1 \}[/mm]
> [mm]\delta(Z1, 0) = \{Z2 \}[/mm]
(Andernfalls hast du oben Mengenklammern vergessen bei der Vereinigung!)
> Die neuen Zustände sind klar:
>
> Z' = [mm]\mathcal{P}(Z)[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
= {Z0, Z1, Z2, Z0Z1, Z0Z2, Z1Z2,
> Z0Z1Z2, [mm]\emptyset}[/mm]
Ja.
> Doch: Wie komm ich jetzt darauf wie diese vielen neuen
> Zustände korrekt verknüpft werden müssen?
Nehmen wir z.B. den Zustand $Z0Z1 = [mm] \{ Z0, Z1 \}$ [/mm] und die Eingabe $0$.
Dann ist [mm] $\delta'(Z0Z1, [/mm] 0) = [mm] \delta(Z0, [/mm] 0) [mm] \cup \delta(Z1, [/mm] 0) = [mm] \{ Z0 \} \cup \{ Z2 \} [/mm] = [mm] \{ Z0, Z2 \} [/mm] = Z0Z2$ (in deiner Schreibweise).
> Ich verstehe die obige mathematische Notation darüber wie
> [mm]\delta'[/mm] zustande kommen soll nicht. Aber kann es sein, dass
> ich die neuen Zustandsübergänge selbst finden muss?
Nein, du vereinigst einfach die Mengen.
LG Felix
|
|
|
| |
|
Hi und danke für deine Antwort!
Ich zitiere mal diesen Teil:
>
>> Doch: Wie komm ich jetzt darauf wie diese vielen neuen
>> Zustände korrekt verknüpft werden müssen?
>
>Nehmen wir z.B. den Zustand und die Eingabe .
>
>Dann ist (in deiner Schreibweise).
>
>> Ich verstehe die obige mathematische Notation darüber wie
>>zustande kommen soll nicht. Aber kann es sein, dass
>> ich die neuen Zustandsübergänge selbst finden muss?
>
>Nein, du vereinigst einfach die Mengen.
Jetzt habe ich nur noch eine Frage: Wie behandel ich die ganzen Fälle die im NFA einfach nicht abgedeckt wurden?
Ich müsste ja für jeden Zustand die Zustandsübergänge für alle möglichen Eingaben haben. Die hat man bei einem NFA aber ja nicht zwangsläufig.
Z.B. in dem Beispiel von vorhin. Da ist ja jetzt zum Beispiel nicht gesagt was folgendes ist:
[mm] \delta(Z1, [/mm] 1) = ?
Eine Möglichkeit wäre, denke ich, den NFA zunächst mit einem Fangzustand so zu ergänzen, dass jeder Zustand schonmal alle Eingabemöglichkeiten hat. Und mit diesem neuen NFA weiter zu arbeiten.
Oder gibts da eine bessere Lösung?
Danke.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:20 So 13.09.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 06:35 Do 17.09.2009 | | Autor: | felixf |
Hallo!
Sorry das ich erst jetzt antworte, ich war in den letzten Tagen fast nicht hier.
> >> Doch: Wie komm ich jetzt darauf wie diese vielen neuen
> >> Zustände korrekt verknüpft werden müssen?
> >
> >Nehmen wir z.B. den Zustand und die Eingabe .
> >
> >Dann ist (in deiner Schreibweise).
> >
> >> Ich verstehe die obige mathematische Notation darüber
> wie
> >>zustande kommen soll nicht. Aber kann es sein, dass
> >> ich die neuen Zustandsübergänge selbst finden muss?
> >
> >Nein, du vereinigst einfach die Mengen.
>
>
> Jetzt habe ich nur noch eine Frage: Wie behandel ich die
> ganzen Fälle die im NFA einfach nicht abgedeckt wurden?
Nun, in dem Fall ist der Wert von [mm] $\delta$ [/mm] die leere Menge. Sie traegt nichts zur Vereinigung bei.
> Ich müsste ja für jeden Zustand die Zustandsübergänge
> für alle möglichen Eingaben haben. Die hat man bei einem
> NFA aber ja nicht zwangsläufig.
>
> Z.B. in dem Beispiel von vorhin. Da ist ja jetzt zum
> Beispiel nicht gesagt was folgendes ist:
>
> [mm]\delta(Z1,[/mm] 1) = ?
Das ist einfach [mm] $\emptyset$.
[/mm]
> Eine Möglichkeit wäre, denke ich, den NFA zunächst mit
> einem Fangzustand so zu ergänzen, dass jeder Zustand
> schonmal alle Eingabemöglichkeiten hat. Und mit diesem
> neuen NFA weiter zu arbeiten.
> Oder gibts da eine bessere Lösung?
Dieser Fangzustand heisst [mm] $\emptyset$ [/mm] und er ist bereits da.
LG Felix
|
|
|
|
