\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 7}
\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}
Bearbeitet von {\bfseries Dirk Heine}
\subsubsection*{(a)}
$L \cap L^R$ ist nicht kontextfrei. \\[0.3cm]
Begründung: Gegenbeispiel \\
$L = \{a^n b^n c^*\}$ kontextfrei, $L^R = \{c^n b^n a^*\}$ kontextfrei. \\
$L \cap L^R = \{a^n b^n c^n\}$ ist nicht kontextfrei.

\subsubsection*{(b)}
$L \cdot L^R$ ist kontextfrei. \\[0.3cm]
Begründung: \\
Da $L$ kontextfrei ist, gibt es einen NKA, der $u \in L$ akzeptiert. Genauso kann man einen NKA bauen, der $u^R \in L^R$ akzeptiert. Laut den Abschlusseigenschaften für kontextfreie Sprachen (vgl. Vorlesung) ist $L \cdot L^R$ kontextfrei, wenn $L$ und $L^R$ kontextfrei sind.

\subsubsection*{(c)}
$\{ww^R \; | \; w \in L\}$ ist nicht kontextfrei. \\[0.3cm]
Begründung: Gegenbeispiel \\
$L = \{a^n b^n\}$ ist kontextfrei. \\
$L' = \{ w w^R | w \in L \} = a^n b^n b^n a^n = a^n b^{2n} a^n$.
$a^n b^{2n} a^n$ ist nicht kontextfrei.

\newpage

\section*{Aufgabe 2}
Bearbeitet von {\bfseries Jan Hendrik Dithmar} \\[0.5cm]
Zu zeigen:
$$\text{reguläre Sprachen} \Leftrightarrow \text{rechtslineare Sprachen}$$
Beweis: \\
Es wird gezeigt:
$$\text{Automat} \Leftrightarrow \text{rechtslineare Grammatik}$$
\begin{itemize}
	\item \glqq $\Rightarrow$\grqq : \\
		Bei dem Automaten wird jeder Zustand ein Nichtterminal. Es wird für jeden möglichen Übergang $a \stackrel{b}{\rightarrow} c$ eine Regel der Form $a \rightarrow bc$ erzeugt; für jeden Endzustand eine Regel der Form $a \rightarrow \varepsilon$.
	\item \glqq $\Leftarrow$\grqq : \\
		Für jede Regel der Form $A \rightarrow t_1 ... t_n B$ müssen Zustände angelegt werden: $q_1,...,q_{n-1}$. Dann benötigt man Übergänge der Form $A \stackrel{t_1}{\rightarrow} q_1, q_1 \stackrel{t_2}{\rightarrow} q_2$, ... $q_{n-2} \stackrel{t_{n-1}}{\rightarrow} q_{n-1}, q_{n-1} \stackrel{t_n}{\rightarrow} B$.
\end{itemize}


\newpage

\section*{Aufgabe 3}
Bearbeitet von {\bfseries Jan Hendrik Dithmar}
\subsubsection*{(a)}
Idee (und gleichzeitig Begründung): \\
Um von einer Quadratzahl zur nächsten zu kommen muss man eine ungerade Zahl, die immer um 2 größer als die letze ist, addieren.
\begin{eqnarray*}
	\text{letzte Quadratzahl} & \stackrel{+x}{\rightarrow} & \text{neue Quadratzahl} \quad x \in \{1,3,5,7,...\}\\
	0 & \stackrel{+1}{\rightarrow} & 1 \\
	1 & \stackrel{+3}{\rightarrow} & 4 \\
	4 & \stackrel{+5}{\rightarrow} & 9 \\
	9 & \stackrel{+7}{\rightarrow} & 16
\end{eqnarray*}
Lesen wir zu Beginn ein $a$ auf dem Eingabeband, so schreiben wir ein $a$ auf das Arbeitsband. Wir bewegen den Eingabekopf nach rechts. Ist das Wort auf dem Eingabeband noch nicht zu Ende, so bewegen wir den Arbeitskopf nach rechts, schreiben 2 $a$'s auf das Arbeitsband und bewegen den Arbeitskopf nach links an den Anfang des Wortes auf dem Arbeitsband (Arbeitskopf steht auf dem ersten Zeichen). Nun bewegen wir wieder beide Köpfe nach rechts. Wird auf dem Arbeitsband ein $\overline{b}$ (Leerzeichen) gelesen obwohl das Wort auf dem Eingabeband noch nicht zu Ende ist, schreiben wir wieder 2 $a$'s, fahren den Arbeitskopf nach links und beginnen erneut mit dem Algorithmus. \\
Wird jetzt jedoch auf dem Arbeitsband ein $\overline{b}$ gelesen und ist das Wort auf dem Eingabeband ebenfalls zu Ende, so akzeptiert die TM. Ist das Wort auf dem Eingabeband zu Ende, das nächste Zeichen auf dem Arbeitsband aber kein $\overline{b}$, so akzeptiert die TM nicht.

\newpage
\noindent Turing Maschine: \\[0.5cm]
$Q$ Zustandsmenge \\
$Q=\{s, q_1, q_2, q_3, q_4, h\}$ \\
$\Sigma = \{a\}^*$ \\
$\Gamma = \{a, \overline{b}\}$ \\
$\overline{b} \in \Gamma$ Leerzeichen \\
$s \in Q$ Startzustand \\
$F \subset Q$ Endzustände \\
$F = \{h\}$ \\[0.5cm]
\begin{math}
	(s, a, \overline{b}, s, +1, a, 0) \\
	(s, a, a, q_1, 0, a, +1) \\
	(s, \varepsilon, a, h, 0, a, 0) \\
	(s, \varepsilon, \overline{b}, h, 0, \overline{b}, 0) \\
	(q_1, a, \overline{b}, q_2, 0, a, +1) \\
	(q_2, a, \overline{b}, q_3, 0, a, 0) \\
	(q_3, a, a, q_3, 0, a, -1) \\
	(q_3, a, \overline{b}, q_4, 0, \overline{b}, +1) \\
	(q_4, a, a, q_4, +1, a, +1) \\
	(q_4, a, \overline{b}, q_1, 0, \overline{b}, 0) \\
	(q_4, \varepsilon, \overline{b}, h, 0, \overline{b}, 0)
\end{math}

\end{document}
