Informatiker Board | Theoretische Informatik

Informatiker Board » Themengebiete » Theoretische Informatik » NEA in DEA umwandeln

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Seiten (2): « vorherige 1 [2]

NEA in DEA umwandeln

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

dieAnna
Grünschnabel

Dabei seit: 30.01.2011
Beiträge: 5

Zitatantwort auf diesen Beitrag erstellen

"b: Mit b kommst du von 1 nach 2 aber auch von 2 nach 1. Also muss auch hier eine Schlaufe hin." ---> genau das check ich nicht.

30.01.2011 22:44

Nehmen Sie dieAnna in Ihre Freundesliste auf

ed209
Routinier

Dabei seit: 07.09.2006
Beiträge: 324

Angenommen der Zustand ist im NEA ist entweder 1 oder 2 und es kommt ein b. Dann ist der Folgezustand im Falle einer 1 gleich 2 und im Falle einer 2 ist er gleich 1. Aus einem {1,2} wird also ein {2,1} was dasselbe ist.
Methodisch gehst du so vor: Du nimmst bei einer Menge von Zuständen die möglichen Folgezustände von jedem Zustand und vereinst die.
In deinem Fall: NFA (1,b) = {2} und NFA (2, b) = {1} und die Vereinigung von {2} und {1} ist {1,2}

Ich bin mir nicht ganz sicher ob das deine Frage beantwortet.

Jedoch denke ich daß in der Grafik ein Fehler ist: In dem DEA müsste {1,2} ein gültiger Endzustand sein. Davon ausgehend daß die dick umrandeten grünen Zustände Endzustände sind.

Gruß,
ED

30.01.2011 23:21

Nehmen Sie ed209 in Ihre Freundesliste auf

dieAnna
Grünschnabel

Dabei seit: 30.01.2011
Beiträge: 5

Oh mist, jetzt hab ich den beitrag gelöscht, weil ich nich gesehen hab, dass du geantwortet hast und es mir inzwischen klar wurde.
vielen dank, trotzdem! smile

Ach und ich hätt da noch ne andere Frage, zur Automatenminimalisierung:
man stellt ja so eine Tabelle auf (siehe Schöning--> theoretische Informatik - kurzgefasst) in der alle zustandspaare auftauchen.

dann markiert man all die paare, die nen endzustand enthalten.

dann schaut man bei den restlichen nach, wo man landet, wenn man bei beiden (z.b.) ein a liest und checkt dann, ob die beiden zustände, in denen man landet bereits markiert sind. ist dies der fall, markiert man auch das zustandspaar, von dem man ausgegangen ist.

meine frage: wenn mein alphabet aus a und b besteht. muss ich dann von jedem zustandspaar den "test" machen?

Beispiel:

Zu überprüfen: (q1-q2)
Dann prüfe ich (q1, a) = ?
und (q2, a) = ??

Und schau dann, ob (? - ??) bereits markiert ist. falls ja: markiere ich auch (q1 - q2).

FALLS NEIN, versuche ich dasselbe mit "b" oder?

LG, dieANNA

31.01.2011 00:18

ed209
Routinier

Dabei seit: 07.09.2006
Beiträge: 324

Wenn ich jetzt nichts vergessen habe: Zwei Zustände (q1 und q2) sind äquivalent, wenn für jede Eingabe x des Alphabets die Folgezustände f(q1,x) und f(q2,x) äquivalent sind und entweder q1 und q2 Endzustände oder q1 und q2 keine Endzustände sind.

Gruß,
ED (der jetzt langsam ins Bett muß)

PS: Wenn ich mich recht entsinne macht man die minimierung normalerweise auf den deterministischen Automaten, wenn du da einen Zustand {q1,q2} hast, dann betrachte das als einen unabhängigen Zustand. (kannst den dann auch in q3 umbenennen, das ist wengier verwirrent).

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von ed209: 31.01.2011 00:49.

31.01.2011 00:47

Gast
unregistriert

RE: NEA in DEA umwandeln

Hi,

also Pumping Lema besagt in meiner Kurzfassung, "es ist möglich an einer Stelle eines Wortes dieses Wort beliebig stark aufzublähen".
Somit wenn du dir nochmals die deine Sprache anschaust, wirst du feststellen, dass an dieses realisierbar ist an denn,
i≠j≠k und du kannst dein Wort ab der Stelle i bis zu Stelle k beliebig mit x^j aufblähen.

09.02.2011 01:12

Blackarro Blackarro ist männlich