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 0 Minuspunkte
52 Aufrufe

Gibt es hier einen Tip, wie man auf den regulären Ausdruck kommt?

Ich hatte 011*00*1(100*1 + 00*1)*. Leider ist die angegebene Lösung 01(0 + 1)*01 viel kürzer und prägnanter. Ist meine Lösung falsch und woran sehe ich, dass es viel kürzer geht?

Dankeschön!

in END-AG von Dozent (10.1m Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte
 
Beste Antwort
Hi,
 
deine Lösung ist leider falsch. Das Wort 011101 ist Teil der Sprache und wäre mit deinem regulären Ausdruck nicht zu erzeugen. Um den regulären Ausdruck zu erhalten, betrachtet man am besten den nichtdeterministischen Automaten oder die Definition der Sprache, der deterministische Automat ist meistens deutlich komplizierter. 
Die Sprache ist so definiert, dass am Anfang und am Ende immer 01 stehen müssen und die Zeichenanzahl mindestens 4 beträgt. Wenn am Anfang und am Ende 01 stehen, ist die Bedingung zur Zeichenanzahl ja schon automatisch erfüllt. Dazwischen können noch beliebige Zeichen stehen, deshalb fügt man im regulären Ausdruck (0 + 1)* ein. 
Wenn man den nichtdeterministischen Automaten bretrachtet erkennt man gleichermaßen, dass die Wörter die Form 01(beliebige Zeichen)01 haben und erhält so den regulären Ausdruck.
 
Gruß,
Jonas (Tutor) 
von Dozent (10.1m Punkte)  
...