Verständnisproblem mit Musterlösung und alternative Lösung

Question

Bei der Aufgabe lautet die Musterlösung:

(Ich habe die kritischen Stellen unterstrichen, damit schneller klar wird worüber ich spreche)

α =(000* + Ø*)1(0 + 1)*0 + 00*(1 + 10 + Ø)

Müsste es nicht korrekterweise

α =(00*0 + Ø*)1(0 + 1)*0 + 00*(1 + 10 + Ø)

lauten?

Man geht doch im Zustandsdiagramm des nichtdeterministischen Automaten in diesem Fall von Zustand S0 über Eingabe von 0 in Zustand S1, wo beliebig viele Iterationen von 0 auftreten können, bevor man über Eingabe von 0, wieder in Zustand S0 zurückkehrt.

Außerdem würde mich interessieren ob auch die Lösung

α =(00*0 + Ø*)1(0 + 1)*0 + 00*(1 + 10 + Ø*)

richtig ist. Oder einigt man sich auf die Konvention, dass das Ø-Zeichen nicht iteriert wird?

Mit freundlichen Grüßen 

Raphael

Answer 1

Hallo Raphael,

 

was Ihre erste Frage angeht, sind die beiden Vorschläge 000* bzw. 00*0 äquivalent. Ob man die beiden obligatorischen Nullen am Anfang schreibt oder eine am Anfang und eine nach den optionalen Nullen, ist egal.

 

 

Was Ihren anderen Vorschlag angeht, haben Sie recht, da haben wir uns vertippt. Das müsste eigentlich das leere Wort sein, das in regulären Ausdrücken als Ø* geschrieben wird. Danke für diesen Hinweis, das wird morgen geändert.

 

Viele Grüße

 

Lukas König (Übungsleiter)

Comments

Hallo Herr König,
wäre die Lösung 0(0*+00) + 00*(1+10)+ 1(0+1)0 nicht möglich? Den ersten Teil der Lösung kann ich irgendwie nicht nachvollziehen, wieso 3 mal die 0? Man geht doch vom Startzustand zum Endzustand s1 ,was mit einer 0 geht; danach gehe ich die Optionen von S1 wieder zurück zu 1 durch, sprich (0*+00) dann füge ich ein oder also + hinzu, damit ich auch den Weg von s0 nach s4 abdecke, heißt 00*(1+10)..... Was mache ich falsch, an dieser Aufgabe sitze ich schon so lange.. Danke

---

Sie meinen diesen Ausdruck aus der Lösung: $$(000^\star + \emptyset^\star)1(0 + 1)^\star 0 + 00^\star (1 + 10 + \emptyset^\star)$$
Der erste Teil mit den drei Nullen bezieht sich auf den unteren Teil des Automaten. Nach $(000^\star + \emptyset^\star)1(0 + 1)^\star 0$ ist man sozusagen unten herum nach $s_4$ gelangt und hat dabei auch den Weg über $s_1$ berücksichtigt.

Der zweite Teil $00^\star (1 + 10 + \emptyset^\star)$ deckt den oberen Teil ab. Das ist natürlich nur eine mögliche Lösung, und es kann auch einfachere geben. Ihre schaue ich mir gleich an.

---

Bei Ihrer Variante
$$0(0^\star+00) + 00^\star(1+10)+ 1(0+1)0$$
decken Sie zuerst alle Wege zum Endzustand $s_1$ ab durch $0(0^\star+00)$. Das kann man so machen. Dann gehen Sie den oberen Weg nach $s_4$ durch $00^\star(1+10)$. Auch das ist in Ordnung. Dann gehen Sie den unteren Weg nach $s_4$, und hier müsste es $1(0+1)^\star 0$ heißen, dann sollte aber auch das stimmen.

Soweit ich das sehe, ist Ihre Lösung also (bis auf den kleinen Fehler) auch korrekt. Reguläre Ausdrücke sind nicht ganz intuitiv, aber mit etwas Übung kommt man dahinter, wie es läuft. Dabei darf man aber nicht erwarten, dass man die einfachste Lösung findet, denn das ist i.A. sehr schwer.

---

In diesem Fall finde ich Ihre Lösung eigentlich einleuchtender als unsere.

PS. Diese Frage hätten Sie besser als eigenständigen Post verfasst!

---

Hallo,
ist 0(0*+00)+00*⋆(1+10)+1(0+1)*0 das wirklich richtig?
Es ist mit diesem Ausdruck doch nicht möglich die s0-s1 Schleife beliebig oft zu wiederholen und anschließend dann über den unteren Weg zu s4 zu gelangen. Bsp: 0001010 ?

---

Du hast recht, so ist es nicht richtig. Die Schleife fehlt (über s1 und s0 zu s4 zu kommen)