\section{Unentscheidbare Grammatikprobleme} \inhalta{6-12} \only
{\begin{frame} Wir hatten im Kapitel über die regulären Sprachen gesehen, dass alle Fragen, die wir dort über reguläre Sprachen gestellt hatten, entscheidbar waren. Später hatten wir aber angemerkt, dass es zu kontextfreien Sprachen Fragestellungen gibt, die nicht entscheidbar sind. Damals hatten wir den Nachweis aber in Ermangelung eines präzise definierten Entscheidbarkeitsbegriffs noch nicht führen können. Mittlerweile haben wir einen präzise definierten Entscheidbarkeitsbegriff kennengelernt. In diesem Kapitel werden wir nun mit Hilfe der Unentscheidbarkeit des Postschen Korrespondenzproblems nachweisen, dass einige Fragestellungen aus dem Bereich der kontextfreien und kontextsensitiven Grammatiken nicht entscheidbar sind. Sie betreffen das Schnitt-, das Endlichkeits- und das \"Aquivalenzproblem. \end{frame}} \begin{frame} \begin{theorem} Die folgenden Fragestellungen sind unentscheidbar: \pause Gegeben seien zwei kontextfreie Grammatiken $G_1$ und $G_2$. \pause \begin{enumerate} \item Ist $L(G_1) \cap L(G_2) = \emptyset$ ? \pause \item Ist $|L(G_1) \cap L(G_2)| = \infty$ ? \pause \item Ist $L(G_1) \cap L(G_2)$ kontextfrei ? \pause \item Ist $L(G_1) \subseteq L(G_2)$ ?\ \pause \item Ist $L(G_1) = L(G_2)$ ? \end{enumerate} \end{theorem} \only
{ Beweis: (1) Jedem Postschen Korrespondenzproblem $P = \{(x_1, y_1),..., (x_k, y_k)\}$ über dem Alphabet $\{0, 1\}$ können effektiv zwei kontextfreie Grammatiken $G_1=(N_1,T,P_1,S)$ und $G_2=(N_2,T,P_2,S)$ wie folgt zugeordnet werden: $$N_1:=\{S,A,B\},~~~N_2:=\{S,R\},~~~T= \{0, 1, \$, a_1,..., a_k\}$$ } \only{ \pause Beweis: (1) Gegeben Postsches Korrespondenzproblem $P$ über $\{0, 1\}$ \pause mit \[P= \{(x_1, y_1),..., (x_k, y_k)\}\] \pause Konstruiere zwei kontextfreie Grammatiken $G_1=(N_1,T,P_1,S)$ \pause und $G_2=(N_2,T,P_2,S)$ \pause wie folgt: $$N_1=\{S,A,B\},\pause~~~N_2=\{S,R\},\pause~~~T= \{0, 1, \$, a_1,..., a_k\}$$ } \end{frame} \begin{frame} Die Grammatik $G_1$ besitzt die Ableitungsregeln $P_1$ \pause \GLA S&\rightarrow& A\$B\\ \pause A&\pause \rightarrow& \pause a_1Ax_1 \pause\mid ... \mid \pause a_kAx_k\pause\mid a_1x_1\pause \mid ... \mid \pause a_kx_k\\ \pause B&\pause \rightarrow& \pause y_1^{r} Ba_1\pause \mid ... \mid \pause y_k^{r} Ba_k \pause\mid y_1^{r} a_1 \pause\mid ... \mid\pause y_k^{r} a_k \GLE \pause wobei mit $ w^{r}$ das gespiegelte Wort zu $w$ bezeichnet wird.\pause Diese Grammatik $G_1$ erzeugt die Sprache \pause \[L_1 = \pause\{a_{i_1}...a_{i_n}x_{i_n}...x_{i_1}\$ y_{j_1}^{r}...y_{j_m}^{r}a_{j_m}...a_{j_1} \pause\mid n, m \geq 1,\pause i_\nu,j_\mu\in \{1,.., k\}\}\] \pause Betrachte eine zweite Grammatik $G_2$ mit folgenden Regeln $P_2$:\pause \GLA S&\rightarrow& \pause a_1Sa_1 \pause \mid ... \mid \pause a_kSa_k\pause\mid R\\ \pause R&\pause \rightarrow& \pause 0R0 \pause \mid 1R1 \pause\mid \$ \GLE \pause Sie erzeugt die Sprache \[L_2 =\pause \{uv\$v^{r}u^{r} \pause\mid u\in\{a_1,..., a_k\}^*,\pause v\in\{0, 1\}^*\}\] \pause Beide Sprachen sind übrigens sogar deterministisch kontextfrei. \end{frame} \only
{\begin{frame} Das Korrespondenzproblem $P$ besitzt eine Lösung $i_n,..., i_1$, also $x_{i_n}... x_{i_1} = y_{i_n}...y_{i_1}$, genau dann, wenn $L_1 \cap L_2$ nicht leer ist. Im Schnitt liegt dann das Wort: \[w= a_{i_1}...a_{i_n}x_{i_n}...x_{i_1}\$y_{i_1}^{r}... y_{i_n}^{r}a_{i_n}...a_{i_1}\] Man kann sagen, dass das Enthaltensein eines Wortes wie in $L_1$ in $L_2$ erzwingt, dass erstens die verwendeten Indizes bei den den $x_i$ und den $y_j$ die Gleichen sind und dass zweitens das aus den $x_i$ gebildete Wort gleich dem aus den $y_j$ gebildeten Wort ist. Das bedeutet, dass $P \rightarrow$ $(G_1, G_2)$ eine Reduktion von $PCP$ auf das Komplement des Schnittproblems ist. Da $PCP $ unentscheidbar ist, ist also auch das Komplement des Schnittproblems unentscheidbar, und damit auch das Schnittproblem selbst unentscheidbar. \end{frame}} \only{\begin{frame} Idee der Konstruktion:\pause \begin{itemize} \item Jedes Wort $w$ aus $L_1$ bzw. $L_2$ hat vier Komponenten: \pause$w=ab\$c^rd^r$ \pause mit $a,d\in\{a_1,..., a_k\}^*$ \pause und $b,c\in\{0, 1\}^*$\pause \item $L_1$: \pause Indizes der $x_i$ bei $b$ in $a$ \pause bzw.\ der $y_i$ bei $c$ in $d$ \pause beim $PCP$ $P$, \pause \\ aber kein Zusammenhang zwischen $a$ und $d$ \pause oder $b$ und $c$.\pause \item $L_2$: \pause Übereinstimmung $a=d$ bzw. $b=c$, \pause \\ aber keinerlei Verbindung mit $P$\pause \item Schnittbildung: \pause $b$ und $c$ enstehen aus $P$ \pause (wg. $L_1$), \pause sind gleich ($b=c$) \pause und nutzen die gleichen Indizes ($a=d$) \end{itemize} \pause Damit: $P$ besitzt Lösung $i_1,..., i_n$ genau dann, \pause wenn $w\in L_1 \cap L_2$ für\pause \[w= a_{i_n}...a_{i_1}x_{i_1}...x_{i_n}\$y_{i_n}^{r}... y_{i_1}^{r}a_{i_1}...a_{i_n}\] \pause Also: \pause Abbildung $f: P \mapsto (G_1, G_2)$ reduziert $PCP$ auf \pause das Komplement des Schnittproblems. \pause Insgesamt: \pause $PCP $ unentscheidbar \pause \\ $\Rightarrow$ Komplement des Schnittproblems unentscheidbar \pause \\ $\Rightarrow$ Schnittproblem unentscheidbar. \end{frame}} \only
{\begin{frame} (2) Wenn $P$ mindestens eine Lösung besitzt, so besitzt $P$ auch unendlich viele Lösungen, indem man die Lösungsfolge beliebig oft wiederholt. Damit ist das Problem, ob $|L(G_1) \cap L(G_2)| = \infty$ ist, ebenso unentscheidbar, mit der gleichen Reduktion. (3) In dem Falle, dass $L(G_1) \cap L(G_2)$ nicht leer und damit unendlich ist, ist weiterhin $L_1 \cap L_2$ keine kontextfreie Sprache. Wir skizzieren eine Begründung, die auf dem Pumping-Lemma für kontextfreie Sprachen beruht. \\ Nehmen wir einmal an, $L_1 \cap L_2$ wäre kontextfrei. Alle Wörter in $L_1 \cap L_2$ haben die oben angegebene Form $uv\$v^{r}u^{r}$, wobei die Indexfolge der $a_i$ in $u$ gleich der gespiegelten Indexfolge der $x_i$ in $v$ ist und die Indexfolge der $a_i$ in $u^{r} $ gleich der gespiegelten Indexfolge der $y_i$ in $v^{r}$ ist. Ein derartiges Wort besteht also aus vier Wortteilen, die alle voneinander abhängen. Wir wählen nun ein Wort der Form $uv\$v^{r}u^{r}$ aus $L_1 \cap L_2$ derart, dass schon $u$ und $v $ alleine länger als die Pumpingzahl $n$ aus dem Pumping-Lemma sind. Laut dem Pumping-Lemma kann dieses Wort dann in 5 Teilwörter zerlegt werden, von denen die drei inneren zusammen nicht länger als $n$ sind, und Teilwort 2 und 4 nicht beide leer sein dürfen. Beim Aufpumpen der Teilwörter 2 und 4 werden dann höchstens zwei der vier Wortteile von $uv\$v^{r}u^{r}$ verändert. Damit geht aber die spezielle Struktur des Wortes $uv\$v^{r}u^{r}$ verloren, da man zum Erhalten dieser Struktur alle vier Wortteile ändern müsste. \\ Daher ist $L_1 \cap L_2$ nicht kontextfrei und das Problem, die Kontextfreiheit festzustellen, unentscheidbar, wieder mit der gleichen Reduktion. \end{frame}} \only{\begin{frame} (2) Verwende gleiche Konstruktion $P\mapsto (G_1,G_2)$ wie bei (1):\pause \GLA P\in PCP&\Leftrightarrow& \pause \textrm{ es gibt eine Lösung }{\cal I}=(i_1,...,i_n)\textrm{ für }P\\ &\pause \Leftrightarrow&\pause \textrm{ es gibt }\infty\textrm{-viele Lösungen }{\cal I}, {\cal I}{\cal I}, {\cal I}{\cal I}{\cal I},...\textrm{ für }P\\ &\pause \Rightarrow&\pause |L_1\cap L_2|=\infty\\ &\pause \Rightarrow&\pause L_1\cap L_2\neq \emptyset~~~~\pause \Leftrightarrow~~~~ P\in PCP \GLE \pause (3) Wieder gleiche Konstruktion $P\mapsto (G_1,G_2)$, \pause\\ setze $L:= L_1 \cap L_2$\pause Jedes Wort in $L$ hat Form $ab\$c^{r}d^{r}$, \pause mit $a=d$, $b=c$ \pause und 'Index-Übereinstimmung' zwischen $a$ und $b$ \pause bzw.\ $c$ und $d$\pause Also: \pause $a$ ober $d$ bekannt \pause $\Rightarrow$ $ab\$c^{r}d^{r}$ eindeutig festgelegt!\pause Behauptung: \pause Falls $|L|=\infty$, dann $L$ ist nicht kontextfrei \end{frame}} \begin{frame} Annahme: $L$ sei kontextfrei \pause(und unendlich), \pause d.h. Pumping-Lemma für kontextfreie Sprachen sei anwendbar, \pause $n$ sei die Pumpingzahl. \pause Wähle $ab\$c^{r}d^{r}\in L$ mit \pause$n< \pause|a| \pause=|d| \pause\leq |b| \pause=|c|$ \pause Betrachte beliebige Zerlegung $ab\$c^{r}d^{r}=uvwxy$ \pause mit \\ $uwy=uv^0wx^0y\in L$, \pause $|vx|\neq0$ \pause und $|vwx|\leq n$ \pause Fall (1): $|u|\geq |a|$: \pause damit $a$ Präfix von $uwy$, \\ aber $b,c,d$ durch $a$ festgelegt \pause\\ $\Rightarrow$ Widerspruch zu $|vx|> 0$ und $uwy\in L$. \pause Fall (2): $|u|< |a|$: \pause damit $|uvwx|<|ab|$ und $d$ Suffix von $uwy$, \pause\\ aber $a,b,c$ durch $d$ festgelegt \pause\\ $\Rightarrow$ wieder Widerspruch zu $|vx|> 0$ und $uwy\in L$. \pause Damit also: \pause $|L|=\infty \Rightarrow L\textrm{ nicht kontextfrei}$ \pause Zusammen: \GLAA P\in PCP & \pause\Rightarrow&\pause |L|=\infty & \pause\Rightarrow& \pause L\textrm{ nicht kontextfrei}\\ \pause P\not\in PCP &\pause\Rightarrow&\pause L=\emptyset &\pause\Rightarrow&\pause L\textrm{ kontextfrei} \GLEE \end{frame} \only
{\begin{frame} Die weiteren Reduktionen sollen nur skizziert werden. (4) und (5): Man kann ausnutzen, dass die Sprachen $L_1$, $L_2$ tatsächlich sogar deterministisch kontextfrei sind und dass diese Klasse unter Komplementbildung abgeschlossen ist. Sie ist sogar effektiv unter Komplementbildung abgeschlossen, d.h. zu $G_1$ und $G_2$ kann man effektiv Grammatiken $G_1'$, $G_2'$ konstruieren mit $L(G_1') = $Komplement($L_1$) und $L(G_2') = $Komplement($L_2$). Dann folgt \GLA L_1 \cap L_2 = \emptyset &\Leftrightarrow& L_1 \subseteq L(G_2')\\ &\Leftrightarrow& L_1 \cup L(G_2') = L(G_2')\\&\Leftrightarrow& L(G_3) = L(G_2') \GLE Dabei ist $G_3$ eine aus $G_1$ und $G_2$ konstruierte, kontextfreie Grammatik, die die (kontextfreie, aber nicht unbedingt deterministisch kontextfreie) Vereinigung der Sprachen $L_1\cup L(G_2')$ erzeugt. Insgesamt haben wir zwei Reduktionen $P\rightarrow (G_1, G_2')$ bzw. $P\rightarrow (G_3, G_2')$ vom $PCP$ auf das Inklusions- bzw. \"Aquivalenzproblem bei kontextfreien Sprachen. Beide Probleme sind damit unentscheidbar. (Das \"Aquivalenzproblem für deterministisch kontextfreie Sprachen ist bekanntlich entscheidbar). \end{frame}} \only{\begin{frame} (4) und (5): \pause Nutze, dass $L_1$, $L_2$ deterministisch kontextfrei sind \pause Deterministisch kontextfreie Sprachen sind effektiv unter Komplementbildung abgeschlossen: \pause \begin{quote}Zu $G_1$ und $G_2$ kann man effektiv Grammatiken $G_1'$ und $G_2'$ konstruieren \pause mit $L(G_1') = \textrm{ Komplement} (L_1)$ \pause und $L(G_2') = \textrm{ Komplement} (L_2)$. \end{quote} \pause Dann folgt \pause \GLA L_1 \cap L_2 = \emptyset &\Leftrightarrow& L_1 \subseteq L(G_2')\GLE \pause D.h. $P\mapsto (G_1, G_2')$ reduziert $PCP$ \pause auf das Inklusionsproblem kontextfreier Sprachen. \pause Aus $G_1$ und $G'_2$ konstruiere $G_3$ \pause mit $L(G_3) =L_1\cup L(G_2')$, \pause dann \GLA L_1 \cap L_2 = \emptyset &\Leftrightarrow& L_1 \cup L(G_2') = L(G_2')\\ & \pause\Leftrightarrow& \pause L(G_3) = L(G_2') \GLE \pause D.h. $P\mapsto (G_3, G_2')$ reduziert $PCP$ \pause auf das Äquivalenzproblem kontextfreier Sprachen. \end{frame}} \only{\begin{frame} \begin{itemize} \item Inklusions- und Äquivalenzproblem kontextfreier Sprachen damit nicht entscheidbar \pause \item $L_1\cup L(G_2')$ ist kontextfrei, aber i.d.R. nicht deterministisch \pause \item Das \"Aquivalenzproblem für deterministisch kontextfreie Sprachen ist entscheidbar \pause (Senizergues, 1997) \pause \item Nichtentscheidbarkeit des \"Aquivalenzproblems für\\ kontextfreie Grammatiken $\Longrightarrow$\pause Nichtentscheidbarkeit des \"Aquivalenzproblems für \pause \begin{itemize} \item nichtdeterministische Kellerautomaten, \pause \item kontextsensitive Grammatiken,\pause \item LBA's, Turingmaschinen,\pause \item LOOP-, WHILE-Programme \pause \item etc. \end{itemize} \end{itemize} \end{frame}} \begin{frame} \only
{ Mit der Nichtentscheidbarkeit des \"Aquivalenzproblems für nichtdeterministische kontextfreie Grammatiken gilt das Gleiche für nichtdeterministische Kellerautomaten, kontextsensitive Grammatiken, LBA's, Turingmaschinen, LOOP-, WHILE-Programme etc. Da die Sprachen $L_1$ und $L_2$ sogar deterministisch kontextfrei sind, können wir den vorigen Satz noch verschärfen.} \only{$L_1$ und $L_2$ waren deterministisch kontextfrei, damit sogar: \pause } \begin{theorem} Deterministisch kontextfreie Sprachen $L_1$ und $L_2$ seien durch ihre deterministische Kellerautomaten gegeben. \pause Dann sind die folgenden Fragestellungen unentscheidbar: \pause \begin{enumerate}\item Ist $L_1 \cap L_2 = \emptyset$ ? \pause \item Ist $|L_1 \cap L_2| = \infty$ ? \pause \item Ist $L_1 \cap L_2$ kontextfrei ? \pause \item Ist $L_1 \subseteq L_2$ ? \end{enumerate} \end{theorem} \end{frame} \begin{frame} \only
{ Wir erwähnen noch einige weitere Unentscheidbarkeitsergebnisse zu formalen Sprachen. Beweise findet man z.B. im Buch von Schöning, Kapitel 2.8. } \only{ Weitere Unentscheidbarkeitsresultate (ohne Beweis): \pause } \begin{theorem} Betrachte kontextfreie Grammatiken $G$. \pause Dann sind die folgenden Fragen unentscheidbar: \pause \begin{enumerate}\item Ist $G$ mehrdeutig? \pause \item Ist das Komplement von $L(G)$ kontextfrei? \pause \item Ist $L(G)$ regulär? \pause \item Ist $L(G)$ deterministisch kontextfrei? \end{enumerate} \end{theorem} \pause \begin{theorem} Betrachte kontextfreie Sprachen $L_1$ und reguläre Sprachen $L_2$. \pause Es ist nicht entscheidbar, ob $L_1 = L_2$ gilt. \pause \end{theorem} \only
{ Das letzte Ergebnis betrifft kontextsensitive Sprachen und lautet:} \begin{theorem} Das Leerheits- und das Endlichkeitsproblem für Chomsky Typ-1 Sprachen sind nicht entscheidbar. \end{theorem} \end{frame}