DEA nur einen Zustand mehr als NEA

[Wang]

Hallo,

die folgende Aufgabe lässt mir einfach keine Ruhe:

Meine Idee ist, dass man eine leere Menge so einfügt, dass es bzgl. der Akzeptanz der Sprache keine Auswirkungen hat bzw. keine Unterschiede gibt. Mit leerer Menge meine ich soetwas wie in diesem Wikipedia-Beispiel:

Automat zum regulären Ausdruck

Jetzt weiß aber einerseits nicht, ob das stimmt und andererseits auch nicht, wie eine "formale Definition" aussehen soll?

Bin für jede Antwort wie immer sehr dankbar!

Gruß
Wang

 

[XHelp]

Du kannst z.B. das Alphabet um ein Zeichen (z.B.

x

) erweitern, einen neuen Zustand (Fangzustand) z.B.

Y

dazu schreiben und bei jedem Zustand einen

d(z,x) = y

dazuzaubern und alle nicht vorhandenen übergänge auch in diesen Zustand führen.

 

[Wang]

Klingt gut.
Mein Problem ist nur, dass ich nicht weiß, wie ich das hinschreiben soll, den bis auf z_0 ist kein konkreter Zustand gegeben. ???:L

 

[XHelp]

Die konkreten Angaben brauchst du auch nicht. Du kannst es allgemein durch Eigenschaften angeben:
z.B.:

Da sagst du z.B. dass du einen neuen Zustand erzeugst, in dem du zu der alten Menge ein Sybol dazumachst, den es vorher nicht gegeben hat. Das Sigma soll aber gleich bleiben.
Und so weiter. Dann musst du dir noch überlegen wie du z.B. die Menge nicht existierender Übergänge darstellst (wobei es schon in der Aufgabenstellung hast gezeigt wird)

 

[Wang]

Irgendwie habe ich leider doch noch Schwierigkeiten mit der Aufgabe (theoretische Informatik halt...).
Die Idee ist doch die, dass ich das Sigma' des DEA um einen Buchstaben x und die Menge der Zustände Q' um den Zustand Y erweitere, am NEA ändert sich jedoch nichts.

Ich stelle mir das nun so vor; es gibt nun eine tabellarisch gegebene Übertragungsfuktion delta, genauso wie hier: Link

Dann würde ich eine weitere Spalte einfügen, mit der Bezeichnung "x". Ebenso würde ich eine neue Zeile am Ende einfügen mit der Zustandsmenge S_4' = {Y}.

Allerdings habe ich das Gefühlt, dass mein letzter Schritt der totale Quark ist, nur stehe ich irgendwie total auf dem Schlauch.


Danke für die Geduld und Mühe!

 

[XHelp]

Ja, Sigma musst du auch erweitern, habe mich beim Beispiel etwas vertan.
Wenn es ein konkreter NFA wäre, könntest du was mit der Tabelle anfangen. Aber du kannst keine Übergangstabelle aufstellen von einem NFA, der du nicht kennst, deswegen musst du alles allgemeingültig machen. Zur Not schreibst du einfach die Zeile aus meinem letzten Post mit

DFA = (...

ab und erklärst den Rest mit eigenen Worten.