NFA -> DFA und Table-filling algorithmus

Pitt_1982 · Anmeldungsdatum: 27.06.2006 Beiträge: 3

Hallo Leute,
kann mir irgendeiner an einem beispiel mit erläuterung zeigen wie man NFA in DFA umwandelt (potenzmengenkonstruktion- hab beispiele gesehen,aber kann das net nachvollziehen) und zweitens: Table-filling algorithmus-genauso, nicht nachvollziehbar für mich.
schreib in 2 wochen klasure und raffe das nicht also bitte helft mir.

MfG
Pitt

ED209 · Anmeldungsdatum: 30.05.2005 Beiträge: 122

Woran genau, hapert es denn?

Pitt_1982 · Anmeldungsdatum: 27.06.2006 Beiträge: 3

ich kenn Potenzmengenkosntruktion und Table-filling algorithmus, aber es ist überall so vollkomplieziert geschrieben. könnt ihr die vorgehensweise irgendwie einfacher berschreiben ( vielleicht mit kleinem beispiel ).
danke

ED209 · Anmeldungsdatum: 30.05.2005 Beiträge: 122

Ich kenne nur die Potenzmengen-Konstruktion, der andere Begriff ist mir nicht gelaeufig. Aber ich hab auch keine Lust noch die Moeglichkeit, hier grafisch ein ganzes Beispiel vorzurechnen.
Vielleicht faengst du schonmal bis zu der Stelle bei der du nicht mehr weiterkommst.

Gruss,
ED209

Pitt_1982 · Anmeldungsdatum: 27.06.2006 Beiträge: 3

wir haben so ein NFA und dazugehöriger DFA, woher kommt das denn beim DFA??: (q0,q1) und (q0,q2) . Kann mir jemand die Vorgehensweise bisschen erklären, wie man so einen nfa in dfa umwandelt??

ED209 · Anmeldungsdatum: 30.05.2005 Beiträge: 122

Die Zustaende im DFA haben als Beschriftung die Menge der Zustaende aus dem NFA, die mit der eingebenen Zeichenfolge erreichbar sind.

Es beginnt mit der Menge {q0}. Wird nun eine 1 eingeben sind zwei Folgezustaende moeglich: q0 und q1. Deswegen zeigt die Menge {q0} im DFA auf die Menge {q0,q1} usw.

http://de.wikipedia.org/wiki/Potenzmengenkonstruktion