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 nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

0 Pluspunkte 1 Minuspunkt
46 Aufrufe

Zu b.)

α2=(0+ø*)(ø*+11*(0+ø*))* korrekt?

Zu c.)

α3=(0+00+ø*)(11*+0+00)* korrekt?

 

in REC-AJ von utdbu utdbu Tutor(in) (107k Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte

Hi,

deine Lösung für b) ist richtig.

bei c) musst du deine Lösung leider nochmal etwas überarbeiten, wegeden der beiden + in der zweiten Klammer kann statt 11* auch 0 oder 00 gewählt werden, dies kann man durch das * am Ende der Klammer beliebig oft wiederholen. du müsstest hier beispielweise die erste ausklammern 1(1* + ..), damit sie immer vor den 0en steht.

Gruß,
Jonas (Tutor)

 

von utdbu utdbu Tutor(in) (107k Punkte)  
0 0
Das verstehe ich leider nicht ganz.

Wieso kann (01*)* eine beliebige Anzahl von Nullen hintereinander produzieren?

Ich hab dies bis jetzt immer so verstanden, das hier z.B. 010111101 herauskommen kann. Mein Lösungsvorschlag zur b) ist:

1*(01*)*0(0+1)
0 0
Dein Vorschlag ist leider aus mehreren Gründen nicht richtig:

- Alle Wörter, die sich mit diesem Ausdruck erzeugen lassen, enden wegen 0(0+1) entweder auf 00 oder 01. Ersteres ist in der Sprache verboten, da nie zwei 0 hintereinander kommen dürfen. Außerem gibt es Wörter in der Sprache, die auf mehreren 1 enden, z.B. 10111

- Mit (01*)* kann man beliebig viele 0 hintereinander erzeugen, da * "beliebig oft, auch nullmal" heißt. Daher muss die Klammer keine 1 erzeugen und durch den äußeren Stern hängt man dann die Nullen hintereinander.

- Die "mittlere" 0 kann nicht weggelassen werden, daher enthält jedes erzeugte Wort mindestens eine 0. Aber beispielsweise ist 111 in der Sprache, kann aber nicht erzeugt werden.

Tobias (Tutor)
...