\documentclass[12pt]{article}

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

\thispagestyle{empty}

\title{Theoretische Informatik (WS 2005/2006) - Übungsblatt 5}
\author{Jan Hendrik Dithmar - Matrikelnummer 2031259 \\
		Do, 11-13 Uhr, Vasileios Anastasatos
	}
\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{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\N}{\ensuremath{\mathbb{N}}}
\newcommand{\C}{\ensuremath{\mathbb{C}}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
\newcommand{\Q}{\ensuremath{\mathbb{Q}}}
\newcommand{\B}{\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}
\subsubsection*{(a)}
$L_1$ ist nicht regulär. \\
Beweis durch Pumping Lemma:
\begin{enumerate}
	\item Gegner wählt ein $N \in \SetN$.
	\item Ich wähle das Wort
		$$z:=a^Nb^{\lfloor\frac{N}{7}\rfloor}$$
	\item Gegner unterteilt $z=uvw$ mit $|uv| \le N, |v| \ge 1$, z.B.
		$$\overbrace{\underbrace{a \ldots}_u \underbrace{\ldots a}_v}^N \overbrace{\underbrace{b \ldots b}_w}^{\lfloor\frac{N}{7}\rfloor}$$
	\item Ich wähle $i=7$, also $uv^7w$. \\
		$uv^7w \notin L_1$, da $v$ nur aus $a$'s besteht \\
		$\Rightarrow \# a$ in $uv^7w \ge N+7$, aber $\# b = \lfloor\frac{N}{7}\rfloor < \lfloor\frac{N+7}{7}\rfloor = \lfloor\frac{N}{7}\rfloor + 1$
\end{enumerate}
$L_1$ ist jedoch kontextfrei. \\
(Für die Zeichnung gelten folgende Konventionen: $x \in \{A, \mbox{\euro}\}$, \$ steht für \euro, e steht für $\varepsilon$.)
\bild{16}{a1a}{Aufgabe 1 (a)}{a1a}

\newpage
\subsubsection*{(b)}
$L_2$ ist regulär, somit auch kontextfrei.
\bild{18}{a1b}{Aufgabe 1 (b)}{a1b}

\subsubsection*{(c)}
$L_3$ ist nicht regulär. \\
Beweis durch Pumping Lemma:
\begin{enumerate}
	\item Gegner wählt ein $N \in \SetN$.
	\item Ich wähle ein Wort $z$ der Länge $>N$:
		$$z=a^Nb^Nc^{N+N}$$
	\item Gegner unterteilt $z=uvw$ mit $|uv| \le N, |v| > 1$
		$$\underbrace{a \ldots}_{uv} \underbrace{ab \ldots bc \ldots c}_{w}$$
		$$\mbox{mit } \underbrace{a \ldots a}_N \underbrace{b \ldots b}_N \underbrace{c \ldots c}_{2N}$$
	\item Ich wähle $i=2$, also $uv^2w$. \\
		$uv^2w \notin L_3$, da $v$ nur aus $a$'s besteht \\
		$\Rightarrow \# a$ in $uv^2w > N$ \\
		$\Rightarrow \# a + \# b > 2N$ \\
		$\Rightarrow uv^2w \notin L_3$
\end{enumerate}
$L_3$ ist kontextfrei. \\
(Für die Zeichnung gelten folgende Konventionen: $x \in \{A, \mbox{\euro}\}$, \$ steht für \euro, e steht für $\varepsilon$.)
\bild{8}{a1c}{Aufgabe 1 (c)}{a1c}

\subsubsection*{(d)}
$L_4$ ist nicht kontextfrei (und damit auch nicht regulär). \\
Beweis durch Pumping Lemma:
\begin{enumerate}
	\item Gegner wählt ein $N \in \SetN$.
	\item Ich wähle als Wort
		$$z:=a^Nb^Nc^{N^2}$$
	\item Gegner unterteilt $z=uvwxy$ mit $|vwx| \le N$ und $|vx| > 0$
		$$\underbrace{a \ldots}_u \underbrace{ab \ldots}_{vwx} \underbrace{bc \ldots c}_y$$
		$$\mbox{mit } \underbrace{a \ldots a}_N \underbrace{b \ldots b}_N \underbrace{c \ldots c}_{N^2}$$
		Da $|vwx| \le N$ kann $vwx$ nicht $a$'s, $b$'s und $c$'s gleichzeitig enthalten.
	\item Ich wähle $i=0$, also $uv^0wx^0y = uwy$. \\
		$uwy \notin L_4$, da:
		\begin{enumerate}[1.]
			\item Fall: $\# a$ in $uwy < N$ (es fehlt mindestens ein $a$ in $uwy$):
				$$\Rightarrow \# c = N^2, \# b \le N$$
				$$\Rightarrow uwy \notin L_4$$
			\item Fall: $\# c$ in $uwy < N^2$ (es fehlt mindestens ein $c$ in $uwy$):
				$$\Rightarrow \# a = N, \# b \le N$$
				$$\Rightarrow uwy \notin L_4$$
			\item Fall: $\# b$ in $uwy < N$ (es fehlt mindestens ein $b$ in $uwy$):
				\begin{enumerate}[3.1]
					\item $\Rightarrow \# a = N \AND \# c = N^2 \Rightarrow uwy \notin L_4$
					\item $\Rightarrow \# a \le N \AND \# c = N^2 \Rightarrow uwy \notin L_4$
					\item $\Rightarrow \# a = N \AND \# c \le N^2$. \\
						Dann gilt: $\# a \cdot \# b \le N \cdot (N-1) = N^2 - N$. \\
						In diesem Fall gilt zudem:
						$$|vx| = N - \# b + N^2 - \# c$$
						(das sind die in $uwy$ fehlenden $a$'s und $c$'s).
				\end{enumerate}
			Wegen $|vwx| \le N$ folgt $N - \# b + N^2 - \# c \le N$.
		\end{enumerate}
	\begin{eqnarray*}
		N - \# b + N^2 - \# c & \le & N \\
		\Leftrightarrow N^2 - (\# b + \# c) & \le & 0 \\
		\Leftrightarrow N^2 & \le & \# b + \# c \\
		\Leftrightarrow \# c & \ge & N^2 - \# b \\
		\overset{\# b < N}{\Rightarrow} \# c & > & N^2 - N
	\end{eqnarray*}
	Insgesamt also: $\# a \cdot \# b \le N^2 - N < \# c$.
\end{enumerate}
$$\Rightarrow uwy \notin L_4$$

\newpage
\section*{Aufgabe 2}
\subsubsection*{(a)}
Kontextfreie Sprachen sind genau solche Sprachen, die durch Kellerautomaten akzeptiert werden. Daher ist es äquivalent, entsprechende Eigenschaften für die akzeptierenden Automaten zu zeigen. Man führt einen Kellerboden \euro' ein. Man geht wie folgt vor:
\begin{itemize}
	\item Man entfernt die Endzustand-Eigenschaft aller Endzustände von $L$ und $L'$.
	\item Dann macht man auch den Startzustand von $L'$ zu einen gewöhnlichen Zustand und führt neue Übergänge \\[1.5cm]
		zwischen den ehemaligen Endzuständen von $L$ und dem ehemaligen Startzustand von $L'$ ein.
	\item Zusätzlich legt man einen neuen Endzustand an und darauf neue Kanten von den ehemaligen Endzuständen von $L'$ mit \\[1.5cm]
\end{itemize}
Anmerkung: Bei $L$ und $L'$ sei das Kellersymbol o.B.d.A. jeweils \euro.

\newpage
\subsubsection*{(b)}
\begin{itemize}
	\item Man führt einen neuen Endzustand ein, entfernt die Endzustandeigenschaft aller Endzustände und erstellt von diesen auf den neuen Endzustand neue Kanten ein mit: \\[1.5cm]
	\item Zudem erstellt man neue Kanten von den alten Endzuständen zu einem neuen Startzustand mit \\[1.5cm]
	\item Dann erstellt man einen neuen Zustand und Kanten vom neuen Startzustand auf diesen Zustand mit \\[1.5cm]
		sowie von diesem Zustand auf den Endzustand mit \\[1.5cm]
	\item Zuletzt fügt man eine Kante vom neuen zum alten Startzustand, den man in einen normalen verwandelt, ein mit \\[1.5cm]
\end{itemize}

\newpage
\section*{Aufgabe 3}
\subsubsection*{(a)}
$L_5$ ist nicht regulär, aber kontextfrei. \\
Sei $X=\{a,b\}^*$. Dann ist $X$ regulär. $a^nb^mb^ma^n$ ist somit sicher in $X$ enthalten. Aber:
$$\not\exists \mbox{ DEA } M \mbox{ mit } L(M) = \{a^nb^{2m}a^n | n,m \in \SetN\}$$
Beweis durch Pumping Lemma:
\begin{enumerate}
	\item Gegner wählt $N \in \SetN$.
	\item Ich wähle als Wort
		$$z:=a^Nb^{2N}a^N \quad |z| > N$$
	\item Gegner wählt Unterteilung, z.B.
		$$\underbrace{a \ldots}_{uv} \underbrace{ab \ldots b \ldots a}_{w} \quad |uv| \le N, v \ge 1$$
	\item Ich wähle $i=0$. Somit fällt aus $uv$ mindestens ein $a$ weg, womit $\# a$ in $uv^0w < N$, aber $\# b = 2N$ und $\# c = N$.
		$$\Rightarrow uv^0w \notin \{a^nb^{2m}a^n | n,m \in \SetN\}$$
\end{enumerate}
$L_5$ ist kontextfrei.
(Für die Zeichnung gelten folgende Konventionen: \$ steht für \euro, e steht für $\varepsilon$.)
\bild{8}{a3a}{Aufgabe 3 (a)}{a3a} \\
Die Grundidee, die dahinter steckt ist diejenige, dass ein NKA für $L_5$ nicht-deterministisch die Mitte von $ww^R$ bestimmt. Solange $w$ gelesen wird, schreibt der NKA jedes gelesene Zeichen von $w$ auf den Keller. Sobald die Maschine anfängt, $w^R$ zu lesen, nimmt sie immer ein Zeichen herunter. Die Regeln für diesen Automaten berücksichtigen, dass ein Zeichen nur dann vom Keller geholt werden kann, wenn das oberste Kellersymbol mit dem gelesenen Zeichen übereinstimmt. Steht zum Schluss nur noch das Kellerbodensymbol \euro\ auf dem Keller und es gibt von der Eingabe nichts mehr zu lesen, akzeptiert der Automat. 

\subsubsection*{(b)}
$L_6$ ist regulär, denn man kann einen $L_6$ akzeptierenden NEA bauen. \\\\
Idee und Vorgehensweise: \\
Man hat bereits einen NEA $M$, der $X$ akzeptiert. Daher kann man einen NEA $M'$ konstruieren, der $\{w|w^R \in X\}$ akzeptiert, wie man in der Vorlesung gezeigt hat. Man schaltet $M$ und $M'$ parallel und wenn beide nach Abarbeitung von $w$ auf dem gleichen Zustand sind (vorausgesetzt, man behält bei der Umkehrung die Knotennummerierung bei), akzeptiert man $w$, sonst nicht. \\\\
Realisierung: \\
Man kehrt $M$ gemäß Vorlesung um und erhält so $M'$. Man schaltet $M$ und $M'$ parallel und führt dazu einen neuen, den ehemaligen Startzuständen vorgeschalteten Startzustand ein. Als nächstes überführt man den so erhaltenen NEA in einen DEA, wobei Knoten nun $\in Q \times Q$ sind, vorausgesetzt $M$ hatte Knoten aus $Q$. Da die Knotenbezeichner jeweils aus $\SetN$ gewesen seien, erhält man nun Bezeichner aus $\SetN \times \SetN$. Hierbei kommt den Tupeln $\left<k,k\right>, \forall k \in \SetN$, eine besondere Bedeutung zu. Zwischen den beiden repräsentierten Knoten wäre in der ursprünglichen Konstruktion ein $\varepsilon$-Übergang in den Parallelautomaten möglich gewesen, womit das gerade jene Knoten sind, die $w$ akzeptieren. Aus diesem Grund entfernt man die Endzustandeigenschaft jedes Endzustandes und macht dafür alle
$$q \in Q \times Q, q=\left<k,k\right>, k \in \SetN$$
zu Endzuständen. \\
Da dieser Automat durchaus Schleifen enthalten kann, sich die Anzahl der Durchläufe aber nicht \glqq merken\grqq\ muss, da eine Abarbeitung von $w^R$ praktisch implizit erfolgt, benötigt der Automat kein Arbeitsband, somit genügt ein DEA.

\newpage
\section*{Aufgabe 4}
\subsubsection*{(a)}
Die Konkatenation ist nicht abgeschlossen.
\begin{eqnarray*}
	L_1 & = & \{0^i1^i2^j | i,j \in \SetN\} \\
	L_2 & = & \{0^i1^j2^j | i,j \in \SetN\}
\end{eqnarray*}
$\Rightarrow aL_1 \cup L_2$ wird von einem DKA akzeptiert (Akzeptanz durch Abarbeiten des Eingabebandes):
\bild{6}{a4a}{Aufgabe 4 (a)}{a4a} \\
Sei nun $L_3 = \{a^i | i \in \SetN\}$. $L_3$ wird von einem DKA akzeptiert (sogar von einem DEA), aber
$$\underbrace{L_3}_{\mbox{DKA-Sprache}} \circ \underbrace{aL_1 \cup L_2}_{\mbox{DKA-Sprache}}$$ wird nicht von einem DKA akzeptiert, denn: \\
Das $a$ zeigt obigem DKA an, ob er 0en und 1en vergleichen soll (falls $a$ gelesen wird) oder 1en und 2en vergleichen soll (falls kein $a$ zu Beginn gelesen wird). Da nun beliebig viele $a$'s vor $(aL_1 \cup L_2)$ stehen können, kann der DKA nicht entscheiden, ob es ein Wort ist, das zu $L_3$ gehört oder ein $a$, das anzeigt, dass 0en und 1en verglichen werden sollen.

\end{document}