\documentclass[10pt]{article}

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

\thispagestyle{empty}

\title{Theoretische Informatik - Übungsblatt 13 \\
        Übungsgruppe 7 - Mi, 16-18 Uhr \\
        Elena Kvassova}
\author{Jan Hendrik Dithmar (Matrikelnummer 2031259) \\
        Dirk Heine (Matrikelnummer 2030941)}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\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}
\begin{enumerate}[(a)]
    \item   Sei ein Wort $w=w_1w_2w_3w_4w_5\ldots$ gegeben. Nach der Regel
            $h(uv)=h(u)h(v)$ läßt sich die Abbildung des Wortes $w$ in seine
            Zeichen zerlegen:
            \begin{eqnarray*}
                h(w) & = & h(w_1w_2w_3w_4w_5\ldots) \\
                     & = & h(w_1)h(w_2w_3w_4w_5\ldots) \\
                     & = & h(w_1)h(w_2)h(w_3w_4w_5\ldots) \\
                     & = & h(w_1)h(w_2)h(w_3)h(w_4w_5\ldots) \\
                     & = & h(w_1)h(w_2)h(w_3)h(w_4)h(w_5)\ldots) \\
            \end{eqnarray*}
            Der Homomorphismus $h: \Sigma^* \rightarrow \Delta^*$ bildet somit
            jedes Zeichen aus $\Sigma$ auf genau ein Zeichen aus $\Delta$
            \emph{oder} auf $\varepsilon$ ab. Die Zeichen des Wortes können
            vollkommen isoliert betrachtet werden.
            
            \noindent Eine kontextfreie Grammatik definiert sich durch Regeln,
            bei denen auf der linken Seite lediglich ein einzelnes Non-Terminal
            stehen darf, auf der rechten Seite jedoch eine beliebige Kombination
            von Terminalen, Non-Terminalen und auch $\varepsilon$. Um eine
            kontextfreie Grammatik für $h(L)$ zu bauen, brauchen wir also
            lediglich in den Regeln der bereits existierenden kontextfreien
            Grammatik für $L$ die rechte Seite zu verändern. Dort werden alle
            Vorkommen von Terminalen $a$ durch den entsprechenden Wert $h(a)$
            ersetzt. Da ausschließlich die rechte Seite der Regeln verändert
            wird und durch die Änderung die Gültigkeit der Regeln nicht
            beeinflusst wird, ist die Grammatik dann immer noch kontextfrei. \QED
    \item   Zeigen zunächst, dass die $L$ Konkatenation einer kontextfreien
            Sprache $L'$ und einer regulären Sprache $L''$ ebenfalls kontextfrei
            ist. Dazu konstruieren wir einen Kellerautomaten, der $L$ akzeptiert.
            Dazu wird auf der Eingabe zunächst der Kellerautomat von $L'$
            ausgeführt. Während der Ausführung ,,raten`` wir nicht-deterministisch,
            an welcher Stelle das von $L'$ akzeptierte Teilwort endet und das
            von $L''$ akzeptierte Teilwort beginnt. Dazu springen wir jeweils
            mit einer $\varepsilon$-Kante in die Startzustand des endlichen
            Automaten von $L''$. Dieser Automat hat keinen Keller und kann somit
            problemlos in den Automaten $L$ integriert werden. Es ist also
            gezeigt, dass die Konkatenation einer kontextfreien und einer
            regulären Sprache ebenfalls wieder kontextfrei ist. \QED
            
            \noindent Nun untersuchen wir die Aussage, dass $L_1/L_2$ kontextfrei
            ist. Beweis durch Widerspruch. Angenommen die Sprache $L_1/L_2$ sei
            \emph{nicht} kontextfrei. Dann konkatenieren wir eine \emph{nicht}
            kontextfreie Sprache $L_1/L_2$ mit einer regulären Sprache $L_2$.
            Nach Voraussetzung müsste die Konkatenation kontextfrei sein, dies
            stellt jedoch einen Widerspruch zur bereits oben bewiesenen Aussage
            dar. \QED
\end{enumerate}

\section*{Aufgabe 2}
Sei der Kellerautomat $K=(Q,\Sigma,\Gamma,q_0,Z_0,\delta)$, der mit leerem Keller
akzeptiert, gegeben. Seien $q_i \in Q$ die Zustände des Automaten. Wir konstruieren
den Kellerautomaten $K'=(Q',\Sigma,\Gamma',q'_0,Z'_0,\delta')$ wie folgt:
\begin{eqnarray*}
    Q'      & = & \{q'_0\} \\
    \Gamma' & = & Q \cup \Gamma \\
\end{eqnarray*}
Zur Initialisierung des Stacks wird $Z'_0$ verwendet, wobei an unterster Stelle
auf dem Stack alle Initialisierungswerte $a \in Z_0$ in der selben Reihenfolge
stehen. An oberster Stelle auf dem Stack steht der jeweils aktuelle Zustand des
(simulierten) Automaten $K$, bei der Initialisierung also $q_0$.

\noindent Die Überführungsfunktion $\delta'$ bestimmt anhand des obersten Symbols auf dem
Stack immer den aktuellen Zustand von $K$ und verwendet $\delta$, um $K$ entsprechend
auszuführen. Die Überführungsfunktion $\delta'$ definieren wir wie folgt:
$$ q'_0, a, q_i :: S \;\longrightarrow\; q'_0, q''_i :: S' \quad\text{mit } (q''_i, S') = \delta(q_i, a, S) $$
Der Kellerautomat $K'$ akzeptiert, wenn das Eingabewort komplett gelesen ist und
der Stack bis auf einen Zustand $q_i$ leer ist.

\section*{Aufgabe 3}
\begin{enumerate}[(a)]
    \item   Die Transformation von einer kurzen Greibach-Normalform in die
            Chomsky-Normalform überführt werden, in den folgende Ersetzungsregeln
            angewandt werden:
            $$ \begin{array}{cclcccl}
                A & \rightarrow & a   & \quad\Longrightarrow\quad & A  & \rightarrow & a \\
                A & \rightarrow & aB  & \quad\Longrightarrow\quad & A  & \rightarrow & A'B \\
                  &             &     &                           & A' & \rightarrow & a \\
                A & \rightarrow & aBC & \quad\Longrightarrow\quad & A  & \rightarrow & A'D \\
                  &             &     &                           & A' & \rightarrow & a \\
                  &             &     &                           & D  & \rightarrow & BC \\
            \end{array} $$
    \item   Zum Angeben von oberen Schranken für $|V'|$ und $|P'|$ reicht es den
            schlimmstmöglichen Fall zu betrachten. Der schlimmstmögliche Fall ist
            offensichtlich $A \rightarrow aBC$, da dann potentiell zwei neue Regeln
            und zwei neue Non-Terminale eingeführt werden müssen.
            
            \noindent Im schlimmsten müssen wir $|P|$ Ersetzungen vornehmen, da wir $|P|$
            Regeln haben, die potentiell geändert werden müssen. Für jede
            Regel aus $G$ können im schlimmsten Fall zwei neue Regeln und zwei
            neue Non-Terminale notwendig sein. Die würde bedeutet, dass
            schlimmstenfalls $2 \cdot |P|$ neue Regeln und $2 \cdot |P|$ neue
            Non-Terminale eingeführt werden müssen.
            
            \noindent Die neuen Regeln der Form $A' \rightarrow a$ sind in ihrer Anzahl
            jedoch durch die Anzahl der Terminale beschränkt, da jedes für diese
            Ergänzungen eingeführte Non-Terminal auf genau ein Terminal abbildet.
            Dadurch lässt sich die Anzahl der Ergänzungen dieser Art zusätzlich
            auf die Anzahl der Terminale beschränken.
            
            \noindent Insgesamt gelten also folgende obere Schranken:
            \begin{eqnarray*}
                |V'| & \le & |P| + \min(|P|, |T|) \\
                |P'| & \le & |P| + \min(|P|, |T|)
            \end{eqnarray*}
\end{enumerate}

\end{document}
