Anubisx

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

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 }

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:

Ä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}^+

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

Der Automat akzeptiert aber auch wwyybw und ist somit falsch