Entscheidbarkeit 49

Wortproblem

Das Wortproblem (gegeben: $x$, gefragt: ist $x\in L\left(G\right)$ bzw. $x\in T\left(M\right)$) ist mit Hilfe eines DFA leicht möglich. Verfolge einfach Zeichen für Zeichen die Zustandsübergänge im Automaten, die durch die Eingabe $x$ hervorgerufen werden. Falls ein Endzustand erreicht wird, liegt $x$ in der Sprache. Die Laufzeitkomplexität beträgt hier $O\left(n\right)$.

Leerheitsproblem

Das Leerheitsproblem stellt bei gegebenem $G$ (bzw. $M$) die Frage, ob $L\left(G\right)=\emptyset$ (bzw. $T\left(M\right)=\emptyset$). Sei $M$ ein gegebener Automat für die Sprache. $T\left(M\right)$ ist genau dann leer, wenn es keinen Pfad vom (einem) Startzustand zu einem Endzustand gibt.

Endlichkeitsproblem

Das Endlichkeitsproblem stellt bei gegebenem $G$ (bzw. $M$) die Frage, ob $\left\vert L\left(G\right)\right\vert<\infty$ (bzw. $T\left(M\right)<\infty$), also ob die definierte Sprache endlich oder unendlich ist.

Hier gibt es zwei Verfahren:

• Sei $n$ die Pumping Lemma (siehe sub:Das-Pumping-Lemma) Zahl zu $L$. Es gilt:
  $$\left\vert L\right\vert=\infty\Leftrightarrow\exists_{L}^{x}:\left\vert x\right\vert\geq n\wedge\left\vert x\right\vert<2n$$
  • Diese Argument verläuft so, dass alle Wörter der Länge $\geq n$ und $<2n$ auf Mitgliedschaft in $L$ geprüft werden müssen.
  • Die Laufzeitkomplexität beträgt $O\left(c^{n}\right)$
• Es ist $\left\vert T\left(M\right)\right\vert=\infty$ genau dann, wenn es in dem von Startzustand erreichbaren Teilgraphen einen Zyklus gibt, und wenn von diesem Zyklus aus ein Endzustand erreichbar ist.
  $$\exists_{\mathrm{Startzustand}}^{z_{0}}:\exists_{\mathrm{Zustand}... ...{z_{2}}:\quad z_{0}\Rightarrow^{*}z_{1}\Rightarrow^{+}z_{1}\Rightarrow^{*}z_{2}$$
  • wesentlich effizienter als erste Methode

Schnittproblem

Das Schnittproblem stellt bei gegebenen $G_{1},G_{2}$ (bzw. $M_{1},M_{2}$) die Frage, ob $L\left(G_{1}\right)\cap L\left(G_{2}\right)=\emptyset$ (bzw. $T\left(M_{1}\right)\cap T\left(M_{2}\right)=\emptyset$). Hierfür muss man eine Sprache (Grammatik) konstruieren, die aus $G_{1}$ und $G_{2}$ hervorgeht, und die beide Grammatiken sozusagen simultan durchläuft. Hiermit ist dieses Problem auf das Leerheitsproblem zurückgeführt.

Äquivalenzproblem

Das Äquivalenzproblem stellt bei gegebene $G_{1},G_{2}$ (bzw. $M_{1},M_{2}$) die Frage, ob $L\left(G_{1}\right)=L\left(G_{2}\right)$ (bzw. $T\left(M_{1}\right)=T\left(M_{2}\right)$). Hierzu gibt es mehrere Lösungsmöglichkeiten:

• Per Minimalautomat:
  • Wenn Sprachen nicht als DFA's vorliegen, diese dahingehend transformieren.
  • Jeweils den Minimalautomaten konstruieren
  • Diese auf Isomorphie (Umbenennung der Variablen) untersuchen, wenn ja, dann sind die Sprachen gleich.
• Rückführung auf Leerheitsproblem:
  $$L_{1}=L_{2}\Leftrightarrow\left(L_{1}\cap\overline{L_{2}}\right)\cup\left(\overline{L_{1}}\cap L_{2}\right)=\emptyset$$

Am Effizientesten ist die Methode des Minimalautomaten, wenn die Sprache bereits als DFA vorliegt. Allgemein ist das Problem NP-hart, hat also eine Laufzeitkomplexität von $O\left(c^{n}\right)$.