Bestimmung von reguläre Ausdrücke wie geht man da vor?

Zb gegeben sei das Alphabet {a, b}. Man soll einen regulären Ausdruck angeben aller Wörter über das Alphabet wo nicht bab vorkommt. Wie geht man da vor?

Answer 1

[ralphdieter]

Ein Wort besteht aus abwechselnden a- und b-Gruppen. Zerlege das Wort an jedem letzten b einer b-Gruppe (z.B. „ab baabb baaa ba“). Die inneren Teile (zwischen zwei b-Gruppen) müssen mindestens 2 a enthalten: baa+b* („a+“ heißt „mindestens ein a“).

Vor der ersten Gruppe darf noch a*b* stehen, und zum Schluss können noch ein paar a folgen.

Alles zusammen: a* b* ( b a a+ b* )* a*