\documentclass[12pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{graphicx}

\thispagestyle{empty}

\title{Theoretische Informatik - Übungsblatt 10}
\author{Jan Hendrik Dithmar - Matrikelnummer 2031259 \\
				Dirk Heine - Matrikelnummer 2030941 \\
		Di, 9-11 Uhr, Andreas Augustin \\
	}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\maketitle

\newpage
\section*{Aufgabe 1}
{\bfseries bearbeitet von Dirk Heine}
\\
\noindent Laut Definition gilt:
$$A \le B \Rightarrow \exists f: \Sigma^* \rightarrow \Sigma^* : w \in A \Leftrightarrow f(w) \in B$$
$$B \le C \Rightarrow \exists g: \Sigma^* \rightarrow \Sigma^* : v \in B \Leftrightarrow g(v) \in C$$
$f$ und $g$ sind total rekursiv und überall definiert.
\\ \ \\
Idee: Wendet man auf eine Eingabe $w$ zunächst die Funktion $g$, und auf das Ergebnis dann die Funktion $f$ an, so ist die Transitivität nach Definition bereits gezeigt.
$$A \le C \Rightarrow \exists h: \Sigma^* \rightarrow \Sigma^* : w \in A \Leftrightarrow h(w) \in C \text{ laut Definition}$$
Sieht man nun die Funktion $h$ als Konkatenation der beiden Funktionen $f$ und $g$ an, so gilt:
$$A \le B \le C \Rightarrow \exists f,g: \Sigma^* \rightarrow \Sigma^* : w \in A \Leftrightarrow g(w) \in B \Leftrightarrow f(g(w)) \in C$$
Also gilt insbesondere auch:
$$A \le C \Rightarrow \exists f,g: \Sigma^* \rightarrow \Sigma^* : w \in A \Leftrightarrow f(g(w)) \in C$$

\noindent Konstruktion: \\
Sei $f$ die zur Reduktion $A \le B$, und $g$ die zur Reduktion $B \le C$ gehörende Funktion. Sei $M_2$ eine (stets haltende) Turing-Maschine, die genau die Wörter aus $C$ akzeptiert. Dann bauen wir eine (stets haltende) Turing-Maschine $M_1$, die genau die Wörter aus $A$ akzeptiert, wie folgt: 
$M_1$ wendet zunächst die Funktion $g$ auf die Eingabe $w$ an, und berechnet $g(w)$. Dann wendet $M_1$ auf $g(w)$ die Funktion $f$ an, und berechnet $f(g(w))$. Dann simuliert $M_1$ auf $f(g(w))$ die Maschine $M_2$ und akzeptiert $w$ genau dann, wenn $M_2$ das Wort $f(g(w))$ akzeptiert. Laut Definition ist dies korrekt.


\newpage

\section*{Aufgabe 2}
{\bfseries bearbeitet von Jan Hendrik Dithmar} \\
Quelle: \glqq Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie\grqq , Hopcroft, 2. Auflage \\[0.5cm]
Behauptung: \\
Ist $L_a$ eine kontextfreie Sprache für die Liste $A$, dann ist $\overline{L}_a$ eine kontextfreie Sprache. \\[0.3cm]
Beweis: \\
Sei $\Sigma$ das Alphabet der Zeichenreihe aus Liste $A=w_1w_2...w_k$ und $I=\{a_1,...,a_k\}$ die Menge der Indexsymbole. Wir entwerfen einen DKA $P$, der $\overline{L}_a$ akzeptiert und wie folgt arbeitet:
\begin{enumerate}
	\item Solange $P$ Symbole aus $\Sigma$ sieht, werden diese auf dem Stack gespeichert. Da alle Zeichenreihen aus $\Sigma^*$ in $\overline{L}_a$ enthalten sind, werden sie im weiteren Verlauf von $P$ akzeptiert.
	\item Sobald $P$ ein Indexsymbol aus $I$ sieht, etwa $a_i$, werdem Symbole vom Stack entfernt und $P$ prüft, ob die obersten Symbole $w_i^R$ bilden. $w_i^R$ stellt dabei die Spiegelung der korrespondierenden Zeichenreihe dar.
		\begin{enumerate}[a)]
			\item Falls nicht, dann ist die bisherige Eingabe sowie jede Fortsetzung dieser Eingabe in $\overline{L}_a$ enthalten. $P$ wechselt daher in einen akzeptierenden Zustand und verarbeitet alle weiteren Eingaben, ohne dabei den Stack zu verändern.
			\item Wurde $w_i^R$ vom Stack entfernt ohne dass die Stackanfangsmarkierung auf dem Stack sichtbar ist, dann akzeptiert $P$, erinnert sich in diesem Zustand jedoch daran, dass nur nach Symbolen aus $I$ gesucht wird und eine Zeichenreihe aus $L_a$ auftreten könnte, die $P$ nicht akzeptiert. $P$ wiederholt solange Schritt 2., wie die Frage nicht gelöst ist, ob die Eingabe in $L_a$ enthalten ist.
			\item Wurde $w_i^R$ vom Stack entfernt und ist die Stackanfangsmarkierung auf dem Stack sichtbar, dann hat $P$ eine in $L_a$ enthaltene Eingabe gesehen und akzeptiert diese Eingabe nicht. Folgen allerdings noch weitere Eingaben, wechselt $P$ in einen Zustand, in dem alle weiteren Eingaben akzeptiert werden und der Stack unverändert bleibt.
		\end{enumerate}
	\item Sieht $P$ nach einem oder mehreren Symbolen aus $I$ ein weiteres Symbol aus $\Sigma$, dann besitzt die Eingabe nicht die korrekte Form einer Zeichenreihe aus $L_a$. $P$ wechselt daher in einen Zustand, in dem er diese sowie alle weiteren Eingaben akzeptiert ohne den Stack zu verändern.
\end{enumerate}


\newpage

\section*{Aufgabe 3}
{\bfseries bearbeitet von Jan Hendrik Dithmar} \\
%\glqq Entscheidbar\grqq\ bedeutet: $\exists$ TM, die auf allen Eingaben $w$ stoppt und genau dann akzeptiert, wenn $w \in L$. \\
%Brauche zum Beweis, dass ein Problem nicht entscheidbar ist, nur eine \glqq Spielkarten\grqq -Folge anzugeben, bei der die TM %nicht aufhört zu rechnen.

\subsubsection*{(a)}
Mit dieser Einschränkung ist das PCP entscheidbar, da das Problem auf die Länge der Strings reduziert wird, wenn das Alphabet nur ein Zeichen enthält. \\
Idee: \\
Es wird dabei angenommen, dass kein Teil enthalten ist, bei dem $|x_i|=|y_i|$, da sonst das Problem trivial lösbar wäre.
\begin{enumerate}
	\item Finde $(x_i,y_i)$ und $(x_j,y_j)$ mit $(|x_i| > |x_j| \AND |y_i| < |y_j|) \OR (|x_i| < |x_j| \AND |y_i| > |y_j|)$. In diesem Fall besitzt das PCP keine Lösung, da die Strings offensichtlich nie gleich lang sein werden können, da mit jeder \glqq Spielkarte\grqq\ der obere oder der untere String immer um mehr erhöht wird als der andere. \\
	$\longrightarrow$ ablehnen und terminieren.
	\item Wurde das Paar gefunden, so ist $I=(\underbrace{i}_{||x_j|-|y_j||-mal},\underbrace{j}_{||x_i|-|y_i||-mal})$ Lösung des PCP.
\end{enumerate}
Beweis:
Zu zeigen:
\begin{eqnarray*}
	|x_i| \cdot ||x_j| - |y_j|| + |x_j| \cdot ||x_i| - |y_i|| & = & |y_i| \cdot ||x_j| - |y_j|| + |y_j| \cdot ||x_i| - |y_i|| \\
	\Leftrightarrow |x_i| \cdot ||x_j| - |y_j|| - |y_i| \cdot ||x_j| - |y_j|| & = & |y_j| \cdot ||x_i| - |y_i|| - |x_j| \cdot ||x_i| - |y_i|| \\
	\Leftrightarrow (|x_i| - |y_i|) \cdot (||x_j| - |y_j||) & = & (|y_j| - |x_j|) \cdot (||x_j| - |y_j||)
\end{eqnarray*}
Durch eine Fallunterscheidung, ob nur $(|x_i| > |x_j| \AND |y_i| < |y_j|)$ oder $(|x_i| < |x_j| \AND |y_i| > |y_j|)$ für das gefundene Paar galt, lassen sich die Betragsstriche entfernen. Für beide Fälle ergibt die Gleichung offensichtlich wahre Aussagen.
\begin{enumerate}
	\item Fall:
		\begin{eqnarray*}
			(|x_i| - |y_i|) \cdot (-|x_j| + |y_j|) & = & (|y_j| - |x_j|) \cdot (|x_i| - |y_i|) \\
			\Leftrightarrow (|x_i| - |y_i|) \cdot (-1) \cdot (|x_j| - |y_j|) & =& (-1) \cdot (|x_j| - |y_j|) \cdot (|x_i| - |y_i|) \\
			\Leftrightarrow -1 & = & -1 \quad \text{(w)}
		\end{eqnarray*}
	\item Fall:
		\begin{eqnarray*}
			(|x_i| - |y_i|) \cdot (|x_j| - |y_j|) & = & (|y_j| - |x_j|) \cdot (-|x_i| + |y_i|) \\
			\Leftrightarrow (|x_i| - |y_i|) \cdot (-1) \cdot (|y_j| - |x_j|) & = & (|y_j| - |x_j|) \cdot (-1) \cdot (|x_i| - |y_i|) \\
			\Leftrightarrow (-1) & = & (-1) \quad \text{(w)}
		\end{eqnarray*}
\end{enumerate}

\subsubsection*{(c)}
Nicht entscheidbar. Beweis durch Gegenbeispiel:
$$\Sigma=\{0,1,2,3,4,5,6,7\}; |\Sigma|=8$$
Spielkarten:
$$(01,0); (10,1); (23,2); (32,3); (45,4); (54,5); (67,6); (76,7)$$
Fängt man z.B. mit $(01,0)$ an, so muss man als nächstes zweimal (10,1) nehmen. Danach muss man wieder $(01,0)$ nehmen; das Spiel geht von vorne los. Die obere Zeile der \glqq Spielkarte\grqq\ bekommt dadurch einen enormen \glqq Vorsprung\grqq , der nicht wieder eingeholt werden kann. Somit läuft die TM ewig und das Problem ist nicht entscheidbar.

\end{document}
