b): Alternative Lösungsvorschläge

Question

Sind die auch richtig?

a=(aa*b+b(a+b)*)*

a=(aa*b)*(b(a+b)*)*

Danke!

 

Answer 1

Hallo,

diese Frage ist wohl unter den Tisch gefallen, deshalb eine späte Antwort:

(aa*b+b(a+b)*)* (Vorschlag weiter oben in diesem Post) ist tatsächlich falsch. Stattdessen könnte es bspw. folgendermaßen heißen:

(aa*b)*b(a+b)*+leereMenge* (diese Lösung ist auch als Musterlösung angegeben).

Auch der zweite Lösungsvorschlag

(aa*b)*(b(a+b)*)*

ist, wenn ich das gerade richtig überblicke, nicht korrekt. Der letzte Stern muss weg und entsprechend fehlt dann noch das leere Wort, wodurch wir wieder bei 

(aa*b)*b(a+b)*+leereMenge*

wären.

Viele Grüße

Lukas König

Answer 2

Ich denke, beide Vorschläge sind korrekt.

Tobias (Tutor)

 

Comments

Wieso ist denn hier der erste Vorschlag korrekt?

Klammer mit * heißt doch, dass der Ausdruck in den Klammern beliebig oft wiederholt werden kann, in dem Fall, dass beliebig oft die Entscheidung zwischen den mit "oder" verknüpften Termen getroffen werden kann.
Wenn ich mich aber einmal für die Variante b(a+b)* entschieden habe komme ich doch nicht mehr aus Zustand s4 heraus, sprich ich könnte mich nicht nochmals für aa*b entscheiden.
Mit erstem Vorschlag ist der obige Post mit a=(aa*b+b(a+b)*)* gemeint.