Theoretische Informatik - Aufgaben

Aufgabe:  

1. Gegeben ist das Alphabet A = {a, b} und der reguläre Ausdruck

   R   =   b(a|b)*  |  (a|b)*bb

   der die Sprache aller Wörter erzeugt, die mit b anfangen oder mit bb enden.

   Konstruieren Sie nach dem unter

   http://hwlang.de/theor/regulaerer-ausdruck-zu-automat.htm

   angegebenen Verfahren auf systematische Art und Weise aus dem regulären Ausdruck R einen nicht­deterministischen endlichen Automaten. Geben Sie die einzelnen Schritte des Konstruktionsverfahrens an.

    

2. Gegeben ist der folgende (deterministische) endliche Automat, der alle Wörter über dem Alphabet A = {a, b} erkennt, die eine gerade Anzahl von b's enthalten.

   

   Erzeugen Sie nach dem unter

   http://hwlang.de/theor/automat-zu-regulaerer-ausdruck.htm

   angegebenen Verfahren aus dem Automaten einen regulären Ausdruck.