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.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin entscheidbarkeit minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

1 Pluspunkt 1 Minuspunkt
115 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

in END-AZ von Dozent (10.1m Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte
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)
von Dozent (10.1m Punkte)  
0 0
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
0 0
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.
0 0
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.
0 0
In diesem Fall finde ich Ihre Lösung eigentlich einleuchtender als unsere.

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