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 turingmaschine pumpinglemma tipp zahlendarstellung cmos bonusklausur klausurrelevant 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 huffman-kodierung cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit hauptklausur vorlesungsfolien polynomialzeitreduktion kontextfreie-sprache faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten mealy lambda endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort moore ohne-lösungen betriebssystem speicherorganisation monotone-grammatik 2-komplement hammingzahl lösungsweg fehler pumping-lemma-für-kontextfreie-sprachen pumping-lemma reguläre-sprache monoton kodierung berechenbarkeit klausureinsicht disjunktive-normalform abzählbarkeit info-ii bussysteme rechnerarchitektur entscheidbarkeit komplexitätsklassen chomsky-klassen ableitungsbaum vorlesungsaufzeichnung round-robin aufzählbarkeit minimierung-endlicher-automaten von-neumann-rechner binärzahl entscheidbar programmiersprachen stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

1 Pluspunkt 1 Minuspunkt
132 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!
0 0
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 ?
0 0
Du hast recht, so ist es nicht richtig. Die Schleife fehlt (über s1 und s0 zu s4 zu kommen)
...