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 sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten 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 klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren

Kategorien

0 Pluspunkte 0 Minuspunkte
65 Aufrufe

Lösung zu 38 b)

(1*(01)*)*(∅*+0)

Hey,
was genau bedeutet der hintere Teil der Lösung, also (∅*+0)?
Wäre der Ausdruck 1*(01*)*1* auch ok?

in Band I, Kapitel 4 von uevhw uevhw Lernwillige(r) (160 Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte
Hallo,

der hintere Teil der Lösung besagt, dass das Wort w auch mit einer einzelnen Null enden kann (rechts in der Klammer die 0) oder eben nicht (links in der klammer die leere Menge). In letzterem Fall würde das Wort also mit einer 1 enden.

Damit ist auch die Frage beantwortet, ob dein Alternativvorschlag eine korrekte Lösung wäre: in deiner Lösung ist nicht vorgesehen, dass das Wort auch mit einer 0 enden kann. Da als Vorgabe für die Sprache aber nur angegeben ist, dass niemals zwei Nullen hintereinander auftauchen dürfen, darf ein Wort auf eine 0 enden, solange davor eine 1 kommt. Deine Lösung deckt diesen Fall nicht ab und ist damit leider nicht korrekt.

Ich hoffe, das hat dir für das Verständnis der Aufgabe geholfen.

 

Viele Grüße,

Nayeli (Tutorin)
von uudlf uudlf Lernwillige(r) (380 Punkte)  
0 0
Hey danke für deine Antwort,

aber bedeutet der Stern nicht, dass die Zahl auch 0 mal vorkommen kann?
Wenn ich also "alle Sterne auf 0 setze" bis auf den vorletzten auf 1, so wäre das Wort doch lediglich die 0.
Die leere Menge kann ich ja auch erreichen, wenn ich dann alle Sterne auf 0 setze.
Oder hab ich das falsch verstanden?
0 0
Hallo,
ich sehe, was du meinst, aber die von dir angegebene Lösung ist trotzdem noch nicht richtig und zwar aus folgendem Grund: wenn du das zweite Sternchen auf 0 setzt, hast du effektiv in der Klammer nur eine 0 stehen. Da außen an der Klammer noch ein * ist, könntest du diese Klammer mit der einen 0 beliebig oft wiederholen, das ist aber laut Definition der Sprache nicht erlaubt.
Ich hoffe, das hilft :)

Viele Grüße,
Nayeli (Tutorin)
0 0
Ah ja stimmt, vielen dank :)
...