✖

Verallgemeinerter nichtdeterministischer endlicher Automat

Kapitoly: Reguläre Ausdrücke, Umwandlung eines regulären Ausdrucks in einen Automaten, Verallgemeinerte NKA, Umwandlung eines Automaten in einen regulären Ausdruck

Ein verallgemeinerter nichtdeterministischer endlicher Automat, abgekürzt ZNKA, ist ein nichtdeterministischer Automat, der nicht nur Symbole aus der Sprache in den Transitionen haben kann, sondern auch einen regulären Ausdruck.

Definition

Wir werden ZNKA während des Algorithmus zur Umwandlung eines endlichen Automaten in einen regulären Ausdruck benötigen. ZNKA ist also ein NKA, dessen Übergänge durch reguläre Ausdrücke definiert sind. Beispiel für einen solchen ZNKA:

Wir sehen, dass z. B. der Übergang vom Zustand q2 zum Zustand q3 führt und durch den regulären Ausdruck $a^\ast b$ bezeichnet wird. Weitere Voraussetzungen für ZNKA:

  • Der Ausgangszustand q0 muss einen Übergang zu allen anderen Zuständen haben. In der Abbildung sehen wir, dass es vom Zustand q0 Übergänge in alle anderen Zustände gibt.
  • Es gibt nur einen Endzustand in ZNKA und alle anderen Zustände haben einen Übergang zu diesem Zustand. Wie in der Abbildung zu sehen ist, haben alle Zustände einen Pfeil, der auf qf zeigt.
  • Der Anfangszustand muss nicht mit dem Endzustand identisch sein. ZNKA kann also mindestens zwei Zustände haben.
  • Alle anderen Zustände, außer dem Anfangs- und Endzustand, müssen Übergänge zu allen anderen Zuständen außer dem Anfangs- und Endzustand haben. Einschließlich Schleifen (Übergang vom Zustand qi zum Zustand qi).

Umwandlung einer normalen NKA in eine ZNKA

Wenn wir eine NKA haben, ist die Umwandlung in eine ZNKA ganz einfach.

  1. Wir erzeugen einen neuen Anfangszustand qs und erstellen einen Epsilon-Übergang zum ursprünglichen Anfangszustand.
  2. Wir erstellen einen neuen Endzustand qf und machen Epsilon-Übergänge von allen ursprünglichen Endzuständen zu dem Zustand qf. Aus den ursprünglichen Endzuständen machen wir normale Zustände.
  3. Wenn es irgendwo mehrere Übergänge gibt (d.h. wenn wir vom Zustand q1 über das Symbol 0 und über das Symbol 1 zum Zustand q2 gelangen), fassen wir diese Regeln zu einem einzigen regulären Ausdruck zusammen und verketten alle ursprünglichen Symbole mit dem Vereinigungsoperator (d.h. wir markieren den Pfeil mit dem regulären Ausdruck 0|1).
  4. Wenn dem Automaten ein Übergang fehlt, der per Definition vorhanden sein sollte, erzeugen wir ihn und markieren ihn mit dem regulären Ausdruck ∅. Dies ändert nichts an der Sprache, die der Automat akzeptiert, da ein solcher Übergang nie gemacht wird.

Wir können diesen Automaten verwenden, um ihn in einen regulären Ausdruck umzuwandeln.