Satz NEA zu regulärer Ausdruck

Einfache Sprache

Wir wandeln erst den NEA in einen GNEA um und dann wenden wir so lange den Satz Zustand aus einem GNEA entfernen an bis wir nur noch Start- und Endzustand haben. Dann gibt es nur noch eine Transition vom Startzustand zum Endzustand. Diese ist beschriftet mit einem Regulärer Ausdruck, der die selbe Sprache erkennt wie der NEA.

Def. Satz NEA zu regulärer Ausdruck

Der Algorithmus NEA2RE wandelt eine NEA in eine Regulärer Ausdruck um

Algorithmus GNEA2RE

  	\begin{algorithm}
	\caption{GNEA2RE}
	\begin{algorithmic}
	\Input $\textrm{GNEA } \mathcal A$
	\While{$\exists q\in Q\setminus\{q_I,q_F\}$}
		\State $\mathcal A = \mathcal A - q$
    \EndWhile
    \return $\mathcal A$
	\end{algorithmic}
	\end{algorithm}

$\mathrm{GNEA2RE}$ hat eine Laufzeit ist $O(Q^2)$ #TODO ?

Algorithmus NEA2RE

  	\begin{algorithm}
	\caption{NEA2RE}
	\begin{algorithmic}
	\Input $\textrm{NEA } \mathcal A$
	\State Turn $\mathcal A$ to a equivalent GNEA $\mathcal B$
    \return \Call{GNEA2RE}{$\mathcal B$}
	\end{algorithmic}
	\end{algorithm}

$\mathrm{NEA2RE}$ hat eine Laufzeit ist $O(Q^2)$ #TODO ?