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

Question

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!

Answer 1

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)