Deterministischer endlicher Automat

[RainerH88]

Hi leute,

schönes Forum habt ihr hier

Kennt sich hier jemand mit DEAs aus?

Ich hab mal einen Ablauf gestaltet in dem geprüft werden soll, ob zwischen einem w und einem y ein bzw. zwischen einem y und einem w ein x vorkommt.

Kann mir einer sagen ob dieser Algorithmus so richtig ist?

Bsp: wwwxy,wxxxyy sind möglich, wwyybw hingegen nicht.

Würde mich sehr freuen, wenn mir jemand helfen könnte.

mfg Rainer

[Klotzkopp]

Dein Automat akzeptiert alle Eingaben außer der leeren Eingabe, weil alle Zustände außer dem Startzustand akzeptierende Zustände sind. Kann also nicht richtig sein.

[RainerH88]

Hi,

vielen Dank für die schnelle Antwort.

Aber der Automat darf doch auch jede (der zulässigen Eingaben w,x,y) Eingabe akzeptieren, oder?

bzw. es ist nicht Pflicht, dass er unbeingt auch mit w anfangen muss. es könnte auch xxyxw heißen

mfg Rainer

[Anubisx]

Der Automat akzeptiert aber auch wwyybw und ist somit falsch

[RainerH88]

ah okay, dann würde ich also noch schleife von start auf start legen, die alle anderen eingaben abfängt.

Würde das reichen?

mfg Rainer

[Enno]

@anubis

wie kann der automat wy aktzeptieren?

[flashpixx]

Versuche doch einen regulären Ausdruck zu finden, den Du dann ganz einfach in einen ea übersetzt. Da reguläre Ausdrücke ebenso wie der ea eine Typ-3-Grammatik / reguläre Grammatik der Chomsky-Hierarchie sind, musst Du nur den regulären Ausdruck als Automaten darstellen.

Folgender regulärer Ausdruck akzeptiert Deine genannten Wörter:

((w+)(x+)(y+))|((y+)(x+)(w+))

wobei Du vielleicht auch einmal definieren solltest, wie oft ein Buchstabe vorkommen sollte, denn nach Deinem Post ist keine Aussage über w und y getroffen. Außerdem hast Du noch den Buchstaben "b" genannt.

Formuliere Dein Problem einmal mit den korrekten Bezeichnungen (Sigma, leeres Wort, etc), dann kann man auch besser helfen.

[Ezra]

Von jedem Deiner Knoten müssen, wenn b,x,y und w als Eingaben zulässig sind, vier Kanten abgehen, sonst ist der DEA nicht ausreichend definiert.

Beispielsweise ist bisher in Zustand "w" nicht definiert, was passiert, wenn ein y eingegeben wird. Da musst Du einfach nur anbauen.

Bearbeitet 2. November 2009 von Ezra

[Anubisx]

@anubis

wie kann der automat wy aktzeptieren?

Da der Automat für jede eingabe ausser dem leeren Wort in der Menge der Endzustände landet und dort auch nicht mehr heraus kommen kann aktzeptiert er {w,x,y}^+ und damit auch wy

[Enno]

Kuck nochmal genau das Bild an. von w gehen doch nur x und w weg. Also kann nach einem w nur ein x oder ein w folgen und kein y.

[Anubisx]

Ähm nein wenn kein Übergang geben ist macht der Automat einfach nichts folglich bleibt er im Endzustand und akzeptiert. Diese Aussage ist jetzt Formal nicht ganz korrekt da per Definition für jede mögliche Eingabe einen Übergang geben muss. Das macht hier allerdings keinen Unterschied denn selbst wenn man einen übergang für y hinzufügen würde er noch aktzeptieren, da er garnicht anderst kann.

Begründung:

Sei L(M) die vom DEA M aktzeptierte Sprache, dann erhalten wir den Komplementärautomaten M' in dem wir alle Nichtendzustände zu Endzuständen machen und alle Endzustände zu Nichtendzuständen machen. Die von M' aktzeptierte Sprache ist dann L(M')=Sigma^*\L(M).

Wenden wir das nun auf unseren Fall hier an stellen wir fest L(M')=leereswort

=> L(M)=Sigma^+={w,x,y}^+

[Enno]

Das PDF http://www.brawer.ch/prolog/endlicheAutomaten.pdf

erklärts auf Seite 12 aber anders.

Kommt der Automat nicht weiter, weil kein bergang

zum aktuellen Eingabezeichen passt, wird die Eingabe

ebenfalls nicht akzeptiert.

[Anubisx]

Hmm dann ist das wohl Definitionsfrage. Aber wenn man das so interpretiert das alle nicht angegeben Übergänge in einen Müllzustand und zu nicht akzeptanz führen stimmt der Automat vielleicht doch so ja was den nun :confused:

[RainerH88]

ööhm, seid ihr mir böse, wenn ich gerade total verwirrt bin xD

was ist denn denn nun mit dem teil? Rein nach der Logik sollte er doch funktionieren. Ich frage mich nur ob meine Endzustände auch wirklich endzustände sind.

mfg Rainer

[Anubisx]

ööhm, seid ihr mir böse, wenn ich gerade total verwirrt bin xD

was ist denn denn nun mit dem teil? Rein nach der Logik sollte er doch funktionieren. Ich frage mich nur ob meine Endzustände auch wirklich endzustände sind.

mfg Rainer

Das hängt ganz davon ab was er den nun wirklich alles akzeptieren soll. Interpretiert man den Automaten so wie in meinem Post davor erwähnt akzeptiert er (((w)+)|x|(w)+x(x|(w)+x)*|(w)+)|((x|(w)+x(x|(w)+x)*y)|y(y|x(x|(w)+x)*y)*|x(x|(w)+x)*|(w)+) :hells:

Oder als Typ 3 Grammatik ausgedrückt G = (N,T,P,s)

G = ({q0,q1,q2,q3},{w,x,y},P,q0)

P = {

q0 -> w q1 | w | y q3 | y | x q2 | x

q1 -> x q2 | x | w q1 | w

q2 -> y q3 | y | w q1 | w | x q2 | x

q3 -> x q2 | x | y q3 | y

}

Bearbeitet 2. November 2009 von Anubisx

[Ezra]

Das PDF http://www.brawer.ch/prolog/endlicheAutomaten.pdf

erklärts auf Seite 12 aber anders.

Da ist der Zustand, in dem er bleibt, aber auch kein Endzustand. (Im Gegensatz zu dem Automaten hier)

[RainerH88]

alles klar, ich hab meinen Automaten dementsprechend umgewandelt.

Eine Frage hab ich noch zu den Endzuständen.

Was ist das eigentlich genau. Sind das die Zustände, wo es passieren kann das sie keine ebene mehr weiter kommen bzw sich in einer endlosschleife verharren?

mfg rainer

[Anubisx]

Endzustände sind jene Zustände bei denen der Automat akzeptiert wenn er nach vollständig gelesener Eingabe darin ist.