Generalisierter nichtdeterministischer endlicher Automat

Einfache Sprache

Im Unterschied zum NEA führt die Transitionsfunktion von einem GNEA nicht zu einem nächsten Zustand, sonder gibt für abhängig zu welchen Zustand man als nächstes möchte einen regulären Ausdruck der auf die Eingabe passen muss.

Def. Generalisierter nichtdeterministischer endlicher Automat

Ein generalisierter nichtdeterministischer endlicher Automat (NEA) ist eine Struktur $(Q,A,\delta,I,F)$ mit:

• $Q$ endliche Menge -> Zustände oder Zustandsmenge
• $A$ endliche Menge -> Eingabesymbole oder Eingabealphabet
• $\delta:(Q\setminus\{q_F\})\times(Q\setminus\{q_I\})\to Reg(A)$ -> Transitionsfunktion
• $q_I\in Q$ -> Startzustand
• $q_F\in Q$ -> Endzustand wobei $q_I \not=q_F$