Home     
    
    Bücher   Links   Impressum

next up previous contents
Nächste Seite: Pumping Lemma für reguläre Aufwärts: Reguläre Sprachen Vorherige Seite: Verknüpfungen regulärer Sprachen   Inhalt

Unterabschnitte

Algorithmen zur Feststellung von Eigenschaften

Das Wortproblem

Das Wortproblem ist die Frage ob ein Wort $w$ in der Sprache des DFAs enthalten ist. Wir simulieren hierfür den DFA. Das Wortproblem kann in linearer Zeit entschieden werden, nämlich in $\Theta(\vert w\vert)$. Für NFAs kann das Wortproblem in exponentieller Zeit gelöst werden, da vorerst der Automat in einen Potenzautomaten umgeformt werden muß, da ein Potenzautomat immer $2^{m}$ Zustände hat, wobei m die Anzahl der Zustände des Orignial-DFAs.

Leerheitstest

Man prüfe, ob der Automat Endzustände hat, die erreichbar sind. Hat er davon keine, so ist die Sprache leer. Andernfalls ist sie es nicht. Beachte, daß wenn der Startzustand Endzustand ist, die Sprache das Wort $\epsilon$ enthält und somit nicht leer ist.
Die Laufzeit hierfür ist $O(\vert Q\vert\cdot\vert\Sigma\vert)$.

Äquivalenztest

Es gilt

\begin{displaymath}L(M_{1})=L(M_{2})\Leftrightarrow L(M_{1})\subseteq L(M_{2})\,\,und\,\,L(M_{1})\supseteq L(M_{2})\end{displaymath}

Für den Inklusionstest $L(M_{1})\subseteq L(M_{2})$ können wir folgendes ausnutzen:

\begin{displaymath}L(M_{1})\subseteq L(M_{2})\Leftrightarrow L(M_{1})\cap \overl... ...tyset \Leftrightarrow L(M_{1}\times \overline{M_{2}})=\emptyset\end{displaymath}

Wir bilden also zwei Mal den Produktautomaten aus
  • einmal der einen Sprache normal und der anderen Sprache negiert und
  • einmal aus der einen Sprache negiert und aus der anderen normal
und schauen, ob beide Automaten die leere Sprache erzeugen. Wenn ja, sind sie äquivalent.
Die Laufzeit für dieses Verfahren ist $O(\vert Q_{1}\vert\cdot\vert Q_{2}\vert\cdot\vert\Sigma\vert)$

Endlichkeitstest

Um zu testen, ob eine Sprache endlich ist, wenden wir auf dem Automaten ähnliche Algorithmen, wie schon aus der Algorithmik bekannt an.
  • Zuerst entfernen wir alle Zustände und die dazugehörigen Kanten, die nicht vom Startzustand aus erreicht werden können.
  • Dann bilden wir den inversen Graphen $G^{-1}$.
  • Wir prüfen, ob von einem Endzustand dieses Graphens irgendein Zyklus erreicht werden kann. Die Zyklen sind genau dieselben, wie in dem Graphen $G$. Wir können Zyklen mit Hilfe der DFS-Kantenklassifizierung finden. Ein Zyklus exisitert dann, wenn es Rückwärtskanten gibt.
next up previous contents
Nächste Seite: Pumping Lemma für reguläre Aufwärts: Reguläre Sprachen Vorherige Seite: Verknüpfungen regulärer Sprachen   Inhalt