Theoretische Informatik - Aufgaben

Aufgabe:  

Geben Sie für jede der folgenden Sprachen über dem Alphabet A = {a, b} einen möglichst einfachen nicht­deterministischen endlichen Automaten an, der sie erkennt.

• L₁  =  Menge aller Wörter, die höchstens ein b enthalten,
• L₂  =  Menge aller Wörter, die das Teilwort bb enthalten,
• L₃  =  Menge aller Wörter, die das Teilwort bb nicht enthalten,
• L₄  =  Menge aller Wörter, die eine ungerade Länge haben.

Zeichnen Sie zunächst den betreffenden nicht­deterministischen Automaten als Zustands­diagramm.

Geben Sie dann die Übergangs­relation des Automaten in die jeweilige unten­stehende Tabelle ein und simulieren Sie den Automaten mit ein paar Eingabe­wörtern.