reguläre Menge zu NEA

[Pandaros]

Mir ist bei der Abbildung 1.9 aus dem Skriptum (S.22 Konstruktion eines Automaten zu einer regulären Menge) nicht klar wieso bei der Konstruktion der "gesternten" Sprache zwei zusätzliche Start- und Endzustände eingefügt werden müssen.

Kann mir bitte jemand weiterhelfen???

[gck]

Mir ist bei der Abbildung 1.9 aus dem Skriptum (S.22 Konstruktion eines Automaten zu einer regulären Menge) nicht klar wieso bei der Konstruktion der "gesternten" Sprache zwei zusätzliche Start- und Endzustände eingefügt werden müssen.

Kann mir bitte jemand weiterhelfen??? Damit man auch mit Epsilon in den Endzustand kommt, weil der Automat A1 im Allg. das Leerwort ja nicht zu akzeptieren braucht:

Die Idee ist, dass man den Automaten für L1 nimmt, Start und Endzustände zu normalen Zuständen macht, von jedem ehemaligen Endzustand eine Epsilonkante zum ehemaligen Startzustand macht. Dann definiert man einen neuen Startzustand und einen neuen Endzustand, wobei man vom neuen Startzustand einerseits per Leerwort direkt in den Endzustand kommt, andererseits vom Startzustand per Epsilon in den "ehemaligen" Startzustand von A1, analog kommt man von den "ehemaligen" Endzuständen auch per Leerwort in den neuen Endzustand.
-> schon hat man aus A1, der die Sprache L1 akzeptiert, einen Automaten A gebaut, der (L1)* akzeptiert...

edit: natürlich schaut die Def. im Skriptum auf den ersten Blick umständlich aus, aber die Variante garantiert, dass es von Links nach Rechts eine "Einbahn" gibt, also wenn ich etwas anderes an den Endzustand anhänge (oder was anderes an den Startzustand angehängt wird), ist garantiert, dass ich nicht plötzlich was bekomme, was ich eigentlich nicht wollte (hoffe, es ist klar, wie ich das meine...)

[Pandaros]

Damit man auch mit Epsilon in den Endzustand kommt, weil der Automat A1 im Allg. das Leerwort ja nicht zu akzeptieren braucht:

Aber wieso kann man die zusätzliche Epsilon-Kante nicht direkt zwischen ursprünglichem Startzustand und ursprünglichem Endzustand einfügen?? :confused:

[gck]

Aber wieso kann man die zusätzliche Epsilon-Kante nicht direkt zwischen ursprünglichem Startzustand und ursprünglichem Endzustand einfügen?? :confused:
Wie weiter unten in meinem Post erwähnt, muss die "Einbahn" sichergestellt sein... Wenn du direkt in den Originalendzustand per Epsilon gehst, kann es ja sein, dass von diesem Endzustand wieder Übergänge ins "Innere" des Automaten möglich sind: möglicherweise würde dein so modifizierter Automat nun andere Worte akzeptiert, die er sonst nich akzeptieren würde:

Beispiel: Stell dir einen Automaten für a+b* vor, der so aussieht, dass es einen Startzustand gibt mit einer a* Schleife, dann einen Endzustand mit einer b* Schleife, diese beiden Zustände sind mit einer a-Kante verbunden. Wenn du jetzt einfach eine Epsilon-Kante vom Startzustand zum Endzustand reingibst, akzeptiert dein Automat plötzlich auch Worte der Gestalt b*, da du jetzt ja nicht mehr über die a-Kante gehen musst, sondern auch die Epsilonkante wählen kannst -> diese Worte gehören aber nicht zu (a+b*)*.

Wenn du den gegebnen Automaten aber ins Konstrukt ausm Skriptum "einspannst", gibt es diese Einbahn und du kriegst genau die Sprache, die du willst...

[Pandaros]

:thumb: .... jetzt ist es mir klar!! Danke