\section{Unentscheidbare Grammatikprobleme}
\inhalta{6-12}
\only<article>{\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<article>{
 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<presentation>{
\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<article>{\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<presentation>{\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<article>{\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<presentation>{\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<article>{\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<presentation>{\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<presentation>{\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<article>{  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<presentation>{$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<article>{
 Wir erwähnen noch einige weitere Unentscheidbarkeitsergebnisse zu formalen Sprachen. 
 Beweise findet man z.B. im Buch von Schöning, Kapitel 2.8.
}
\only<presentation>{
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<article>{
 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}
