Nichtdeterministischer endlicher Automat
Einfache Sprache
Ein Nichtdeterministischer endlicher Automat (NEA) ist ein Endlicher Automat, bei dem es für den Zustandsübergang mehrere gleichwertige Möglichkeiten gibt. Also für manche Eingaben kann gibt es mehrere Folgezustände aus denen (zufällig) ausgewählt werden kann.
Def. Nichtdeterministischer endlicher Automat
Ein nicht-deterministischer 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\times A_\epsilon\rightarrow \mathcal{P}(Q)$ -> Transitionsfunktion mit $A_\epsilon=A\cup\{\epsilon\}$
- $I\in Q$ -> Startzustände
- $F\subseteq Q$ -> Menge der Endzustände
Lemmata
Worttransitionsfunktion eines NEAs erhält Vereinigung
Sei $\mathcal{A}=(Q,A,\delta,I,F)$ NEA, sei $\{R_i\}_{i\in j}$ eine Menge von Teilmengen von $Q$. Bemerke: $R_i\subseteq Q$ Dann gilt:
$$\hat\delta(\bigcup_{i\in j}R_i,w)=\bigcup_{i\in j}\hat\delta(R_i,w)$ f.a. $w\in A^*$$Worttransitionsfunktion eines NEAs erhält Konkatenation
Sei $\mathcal{A}=(Q,A,\delta,I,F)$ NEA und $R\subseteq Q,\;u,v\in A^*$. Dann gilt:
$$\hat\delta(R,uv)=\hat\delta(\hat\delta(R,u),v)$$Äquivalenz der Worttransitionsfunktion aus der Potenzmengenkonstruktion
Sei $\mathcal{A}=(Q^\mathcal{A},A,\delta^\mathcal{A},I^\mathcal{A},F^\mathcal{A})$ NEA, $\mathcal{B}=(\mathcal{P}(Q^\mathcal{A}),A,\delta^\mathcal{B},I^\mathcal{A},F^\mathcal{B})$ der aus $\mathcal{A}$ erzeugt Potenzmengenautomat. Dann gilt für $R\subseteq Q^\mathcal{A}$ und $w\in A^*$:
$$\hat\delta^\mathcal{A}(R,w)=\hat\delta^\mathcal{B}(R,w)$$