Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

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

0 Punkte
66 Aufrufe

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

Gefragt 15, Okt 2014 in END-AZ von Lukas König Dozent (10,065,100 Punkte)  

Eine Antwort

0 Punkte
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)
Beantwortet 15, Okt 2014 von Lukas König Dozent (10,065,100 Punkte)  
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!
...