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

Schöne Ferien!
 

 

Alternative Lösung - wie geht es kürzer?

+1 Punkt
27 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!

Gefragt 15, Okt 2014 in END-AG von Lukas König Dozent (10,065,100 Punkte)  

Eine Antwort

0 Punkte
 
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) 
Beantwortet 15, Okt 2014 von Lukas König Dozent (10,065,100 Punkte)  
...