Die Sprache $L = \{\text{alle Wörter, die auf bb enden}\}$ über dem Alphabet $A = \{\text a,\text b\}$ ist regulär. Es ist sehr einfach, für diese Sprache einen regulären Ausdruck anzugeben, nämlich $(\text a|\text b)^*\text{bb}$.

Auch die Sprache $\bar L = \{\text{alle Wörter, die {\it nicht} auf bb enden}\}$ ist regulär, denn das Komplement einer regulären Sprache ist ebenfalls regulär. Aber für diese Sprache ist es nicht so einfach, einen regulären Ausdruck anzugeben.

Systematisches Vorgehen

Du kannst folgende systematische Methode anwenden, um einen regulären Ausdruck für das Komplement $\bar L$ einer Sprache $L$ zu finden:

1. Du erzeugst aus dem regulären Ausdruck für $L$ einen nichtdeterministischen endlichen Automaten, der $L$ erkennt

2. Du formst diesen Automaten mittels der Teilmengenkonstruktion in einen deterministischen endlichen Automaten um

3. Du wandelst in diesem Automaten alle Endzustände in Nicht-Endzustände um und umgekehrt, sodass der Automat nunmehr $\bar L$ erkennt

4. Du erzeugst aus diesem Automaten den gesuchten regulären Ausdruck für $\bar L$

Bei einem solchen systematischen Vorgehen hast du automatisch die Gewähr dafür, dass du ein korrektes Ergebnis erzielst - vorausgesetzt natürlich, dass du alle Schritte richtig ausführst.

Versuche einmal, diese Methode anzuwenden und einen regulären Ausdruck für die oben genannte Sprache $\bar L$ zu finden.