Verallgemeinerter nichtdeterministischer endlicher Automat

Ein verallgemeinerter nichtdeterministischer endlicher Automat, kurz VNEA, ist ein nichtdeterministischer Automat, der an den Übergängen nicht nur Symbole des Alphabets, sondern auch einen regulären Ausdruck stehen haben kann.

Definition

Den VNEA brauchen wir beim Algorithmus zur Umwandlung eines endlichen Automaten in einen regulären Ausdruck. Ein VNEA ist also ein NEA, dessen Übergänge durch reguläre Ausdrücke definiert sind. Ein Beispiel für einen solchen VNEA:

Wir sehen, dass z. B. vom Zustand q₂ ein Übergang in den Zustand q_f führt, der mit dem regulären Ausdruck a^∗ b beschriftet ist. Weitere Anforderungen an den VNEA:

• Der Startzustand q₀ muss einen Übergang in alle anderen Zustände haben. In der Abbildung sehen wir, dass vom Zustand q₀ Übergänge in alle anderen Zustände führen.
• Im VNEA gibt es nur einen einzigen Endzustand, und alle anderen Zustände haben einen Übergang in diesen Zustand. Wie man in der Abbildung sieht, hat jeder Zustand einen Pfeil, der nach q_f zeigt.
• Der Startzustand darf nicht mit dem Endzustand übereinstimmen. Ein VNEA hat also mindestens zwei Zustände.
• Alle übrigen Zustände außer dem Start- und dem Endzustand müssen Übergänge in alle anderen Zustände haben, außer in den Start- und den Endzustand. Einschließlich Schleifen (Übergang vom Zustand q_i in den Zustand q_i).

Umwandlung eines gewöhnlichen NEA in einen VNEA

Wenn wir irgendeinen NEA haben, ist die Umwandlung in einen VNEA einfach.

1. Wir erzeugen einen neuen Startzustand q_s und einen ε-Übergang in den ursprünglichen Startzustand.
2. Wir erzeugen einen neuen Endzustand q_f und führen von allen ursprünglichen Endzuständen ε-Übergänge in den Zustand q_f. Aus den ursprünglichen Endzuständen machen wir normale Zustände.
3. Wenn irgendwo ein mehrfacher Übergang existiert (d. h., wenn wir vom Zustand q₁ sowohl über das Symbol 0 als auch über das Symbol 1 in den Zustand q₂ gelangen), fassen wir diese Regeln zu einem einzigen regulären Ausdruck zusammen und verbinden alle ursprünglichen Symbole mit dem Vereinigungsoperator (d. h., wir beschriften den Pfeil mit dem regulären Ausdruck 0|1).
4. Wenn im Automaten ein Übergang fehlt, der laut Definition vorhanden sein sollte, erzeugen wir ihn und beschriften ihn mit dem regulären Ausdruck ∅. Dadurch ändern wir die Sprache, die der Automat akzeptiert, nicht, weil ein solcher Übergang nie ausgeführt wird.

Diesen Automaten können wir für die Umwandlung eines Automaten in einen regulären Ausdruck verwenden.