epsilon-Eliminierung

Einfache Sprache

Ziel ist es aus einem NEA einen NEA zu bauen der keine Epsilon-Kanten beinhaltet.

Def. epsilon-Eliminierung

Der NEA $\mathcal A$ und der NEA $\mathcal B$ der durch die Anwendung der Anwendung der epsilon-Eliminierung auf $\mathcal A$ entsteht sind Äquivalente Automaten.

Beiweisidee: Wir geben einen Algorithmus an, der die epsilon-Hülle berechnet:

Beweis:

1. Wieder hole folgende Schritte so lange wie möglich:
   1. Falls Zustände $q,q',q''\in Q$ und eine Eingabesymbol $a\in A$ existiert so, dass die Transitionen $q\overset{a}\rightarrow q'$ und $q'\overset{\varepsilon}\rightarrow q''$ (das ist eine epsilon-Kante) existieren, aber nicht $q\overset{a}\rightarrow q''$, dann füge die Transition $q\overset{a}\rightarrow q''$ hinzu.
   2. Falls Zustände $q,q'\in Q$ existiert so, dass $q\in I$ und eine Transition $q\overset{\varepsilon}\rightarrow q$ existiert, dann mache $q'$ zum Startzustand durch $I_\text{neu} = I_\text{alt} \cup q'$.
2. Entferne alle epsilon-Kante.

#TODO Warum soll das ein Beweis für die Korrektheit sein?

Anwendung der epsilon-Eliminierung

Gegeben den NEA $\mathcal{A}=(Q,A,\delta,I,F)$. Dann ist $\mathcal{B}=(Q,A,\delta',E(I),F)$ einer zu $\mathcal A$ äquivalenter Automat. Wobei

für $x\in A_\varepsilon$ und $q\in Q$.