\documentclass[a4paper]{article}
\usepackage[ansinew]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{ae}
\usepackage[german]{babel}
\usepackage{thumbpdf}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{algorithmic}
\usepackage{float}
\usepackage{color}
\usepackage{alltt}
\usepackage[pdftex,             
            pdfpagelabels,
            colorlinks=true,           % Links nicht farbig umrahmen, sondern als farbigen Text
            urlcolor=colorBlue,        % Farbe für externe Verweise, \href{...}{...}
            filecolor=colorGreen,      % Farbe für lokale Verweise, \href{...}{...}
            linkcolor=colorRed,        % Farbe für interne Verweise, \ref{...} und \pageref{...}
            pdftitle={(Titel)},
            pdfauthor={(Autor)},
            pdfsubject={(Thema)},
            pdfkeywords={(Schlagwörter)},
            pdfpagemode=None,          % Navigationsleiste beim Start ausblenden 
            % pdfpagemode=UseThumbs,     % Thumbnails beim Start anzeigen
            % pdfpagemode=UseOutlines,   % Lesezeichen beim Start anzeigen
            % pdfpagemode=FullScreen,    % im Vollbildmodus starten
            % pdfstartpage=2,            % spezielle Startseite festlegen
            bookmarks,
            % bookmarksopen,             % alle Lesezeichen aufklappen
            % bookmarksopenlevel=2,      % Tiefe, bis zu welcher die Lesezeichen aufgeklappt werden sollen
            bookmarksnumbered,         % Lesezeichen nummerieren
            pdfstartview=FitH,         % Seite auf voller Breite anzeigen
            pagebackref
           ]{hyperref}
\definecolor{colorRed}{rgb}{0.00,0.00,0.00}
\definecolor{colorGreen}{rgb}{0.00,0.00,0.00}
\definecolor{colorBlue}{rgb}{0.00,0.00,0.00}

\title{Theoretische Informatik \\ Übungsblatt 11}                        % Dokumenttitel
\author{Grundmann, Benedikt (Matrikelnr. 2030042) \\
        Fischer, Daniel (Matrikelnr. 2032447) \\ \\
        Übungsgruppe 6, Mittwoch 11-13 Uhr, SR 014}                       % Autor
\date{}                                % kein Datum
% \date{\today}                          % Datum der Erstellung
% \date{(Datum)}                         % manuelle Eintragung des Datums

\DeclareMathOperator{\CSA}{CSA}
\DeclareMathOperator{\FA}{FA}
\DeclareMathOperator{\FF}{FF}
\DeclareMathOperator{\MUX}{MUX}
\DeclareMathOperator{\Enc}{Enc}
\DeclareMathOperator{\Dec}{Dec}
\DeclareMathOperator{\FDec}{FDec}
\DeclareMathOperator{\BCD}{BCD}
\DeclareMathOperator{\BA}{BA}
\DeclareMathOperator{\PP}{PP}
\DeclareMathOperator{\alu}{alu}
\DeclareMathOperator{\testi}{testi}
\DeclareMathOperator{\shifta}{shifta}
\DeclareMathOperator{\IR}{IR}
\DeclareMathOperator{\CLA}{CLA}

\floatstyle{ruled}
\newfloat{schematic}{p}{los}
\floatname{schematic}{Schaltkreis}

\begin{document}

\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetI}{\ensuremath{\mathbb{I}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}} 
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\Set}[1]{\ensuremath{\mathbb{#1}}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\Inv}[1]{\ensuremath{\frac{1}{#1}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\With}{\ensuremath{\:\:|\:\:}}
\newcommand{\BigWith}{\ensuremath{\:\:\Big|\:\:}}
\newcommand{\Vector}[3]{\ensuremath{\left(\begin{array}{c}#1\\#2\\#3\end{array}\right)}}
\newcommand{\degree}{\ensuremath{^\circ}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}

\newcommand{\hrefold}{} \let\hrefold=\href
\renewcommand{\href}[2]{\hrefold{#1}{\textbf{#2}}}
\newcommand{\hyperlinkold}{} \let\hyperlinkold=\hyperlink
\renewcommand{\hyperlink}[2]{\hyperlinkold{#1}{\textbf{#2}}}
\newcommand{\refold}{} \let\refold=\ref
\renewcommand{\ref}[1]{\textbf{\refold{#1}}}
\newcommand{\pagerefold}{} \let\pagerefold=\pageref
\renewcommand{\pageref}[1]{\textbf{\pagerefold{#1}}}

\maketitle
%\tableofcontents

\definecolor{colorRed}{rgb}{0.75,0.00,0.00}
\definecolor{colorGreen}{rgb}{0.00,0.50,0.00}
\definecolor{colorBlue}{rgb}{0.00,0.00,0.75}

\section*{Aufgabe 1}
Kontextsensitive Grammatik für $L = \{a^nb^nc^n \;|\; n \ge 0 \}$:
\begin{eqnarray*}
    S  & \rightarrow & A \\
    A  & \rightarrow & aABC \\
       & \rightarrow & \varepsilon \\
    CB & \rightarrow & BC \\
    aB & \rightarrow & ab \\
    bB & \rightarrow & bb \\
    bC & \rightarrow & bc \\
    cC & \rightarrow & cc
\end{eqnarray*}

\section*{Aufgabe 2}
\begin{enumerate}[(a)]
    \item   Die Sprache $L = \{ a^ib^j \;|\; i^2=j \}$ ist \emph{nicht} kontextfrei.
            Beweis durch Widerspruch zum Pumping Lemma. Das Wort $z=a^{n^2}b^n$ ist
            offensichtlich in $L_1$ enthalten. Es sind drei Zerlegungen $uvwxy$ des
            Wortes $z$ möglich:
            \begin{itemize}
                \item   Sei $vwx=a^s$ mit $s \le n$. Entweder in $v$ oder in $x$ muss
                        mindestens ein $a$ enthalten sein. Konstruieren wir mit $i=0$
                        das Wort $uv^iwx^iy$, erhalten wir $uwy$. In $uwy$ fehlt
                        mindestens ein $a$, so dass $i^2 < j$ gilt. Widerspruch.
                \item   Sei $vwx=b^t$ mit $t \le n$. Entweder in $v$ oder in $x$ muss
                        mindestens ein $b$ enthalten sein. Konstruieren wir mit $i=0$
                        das Wort $uv^iwx^iy$, erhalten wir $uwy$. In $uwy$ fehlt
                        mindestens ein $b$, so dass $i^2 > j$ gilt. Widerspruch.
                \item   Sei $vwx=a^sb^t$ mit $s,t \ge 1$ und $s+t \le n$. Entweder
                        muss in $v$ mindestens ein $a$ oder in $x$ mindestens ein
                        $b$ enthalten sein. Es ist \emph{nicht} zulässig, dass $v$ auch
                        $b$'s enthält und dass $x$ auch $a$'s enthält (da durch $v^i$
                        bzw. $x^i$ sonst $a$'s auf $b$'s folgen könnten, was die Sprache
                        jedoch nicht erlaubt). Sei $k=|v|$ somit die Anzahl der $a$'s in $v$
                        und $l=|x|$ die Anzahl der $b$'s in $x$. Wir wählen $q=0$ und
                        bilden das Wort $uv^qwx^qy=uwy$. Gegenüber dem ursprünglichen
                        Wort $uvwxy=z=a^{n^2}b^n$ sind $k$ weniger $a$'s und $l$ weniger
                        $b$'s in $uwy$ enthalten. Es soll gelten:
                        \begin{eqnarray*}
                            n^2 - k & \stackrel{!}{=} & n - l \\
                            \Longleftrightarrow \quad n^2 - n - (k-l) & \stackrel{!}{=} & 0
                        \end{eqnarray*}
                        Es gilt offensichtlich $0 \le k \le n$ und $0 \le l \le n$.
                        Somit ist $-n \le k-l \le n$. Sei ohne Beschränkung der
                        Allgemeinheit $n \ge 3$. Dann ist $n^2-n-n>0$ und auch
                        $n^2-n-(-n)=n^2-n+n>0$ und somit die Bedingung nicht erfüllt.
                        Widerspruch.
            \end{itemize}
            Weitere Zerlegungen sind offensichtlich nicht möglich. Somit liegt ein
            Widerspruch zum Pumping Lemma vor und die Sprache $L_1$ ist \emph{nicht}
            kontextfrei. \FLASH
    \item   Die Sprache $L_2 = \{ a^ib^j \;|\; i=j \text{ oder } i=2j \}$ ist
            kontextfrei, da wir eine kontextfreie Grammatik für diese Sprache
            bauen können:
            \begin{eqnarray*}
                S   & \rightarrow & S_1 \\
                    & \rightarrow & S_2 \\
                S_1 & \rightarrow & aS_1b \\
                    & \rightarrow & \varepsilon \\
                S_2 & \rightarrow & aaS_2b \\
                    & \rightarrow & \varepsilon
            \end{eqnarray*}
            \QED
    \item   Die Sprache $L_3 = \{ a^ib^jc^k \;|\; i+j=k, \quad i,j,k \ge 0 \}$ ist
            kontextfrei, da wir einen Kellerautomaten bauen können, der die Sprache
            akzeptiert:
            \begin{eqnarray*}
                Q & = & \{q_0,q_1,q_2,q_3\} \\
                \Sigma & = & \{a,b,c\} \\
                \Gamma & = & \{x\} \\
                q_0 & & \text{sei Anfangszustand} \\
                Z_0 & = & \varnothing \\
                F & = & \{q_3\}
            \end{eqnarray*}
            $$ \delta = \begin{cases}
                \quad (q_0, a, S)  & \rightarrow\quad (q_0, xS) \\
                \quad (q_0, b, S)  & \rightarrow\quad (q_1, xS) \\
                \quad (q_1, b, S)  & \rightarrow\quad (q_1, xS) \\
                \quad (q_1, c, xS) & \rightarrow\quad (q_2, S) \\
                \quad (q_2, c, xS) & \rightarrow\quad (q_2, S) \\
                \quad (q_2, \varepsilon, \varnothing) & \rightarrow\quad (q_3, \varnothing)
            \end{cases} $$
            In Zustand $q_0$ wird für jedes gelesene $a$ ein $x$ auf den Stack
            geschrieben. Sobald ein $b$ gelesen wird, wird in $q_1$ gewechselt.
            Weiterhin wird für jedes $b$ ein $x$ auf den Stack geschrieben.
            Auf dem Stack steht also nachdem alle $a$ und $b$ gelesen wurden,
            genau $i+j$ mal das Zeichen $x$. Bei jedem gelesenen $c$ wird ein
            $x$ vom Stack entfernt. Nur wenn der Stack leer ist ($i+j=k$) und
            das Wort komplett gelesen wurde, wird das Wort akzeptiert.
            
            Jede Sprache, für die sich ein Kellerautomat bauen läßt, der diese
            Sprache akzeptiert, ist kontextfrei. Somit ist $L_3$ kontextfrei. \QED
    \item   Die Sprache $L = \{a^nb^nc^n \;|\; n \ge 0 \}$ aus Aufgabe 1 ist offensichtlich eine
            Teilsprache von $L_4$. Wie wir bereits in der Vorlesung gezeigt haben,
            ist die Sprache $L$ \emph{nicht} kontextfrei. Somit ist auch die Sprache
            $L_4$ \emph{nicht} kontextfrei. \FLASH
    \item   Die Sprache $L_5 = \{ v \# w \;|\; v \in \SetB^* \text{ ist Teilwort von } w \in \SetB^* \}$
            ist \emph{nicht} kontextfrei, da man keinen Kellerautomaten bauen
            kann, der die Sprache akzeptiert. Man müsste analog zu Aufgabenteil (f)
            das zu suchende Teilwort auf den Stack bringen. Da das Teilwort nur von
            links nach rechts einmal gelesen werden kann, kann es nur in reversierter
            Reihenfolge auf dem Stack liegen. Somit wäre das \emph{letzte} Zeichen
            des Teilworts das oberste Zeichen auf dem Stack. Da nur das oberste Zeichen
            des Stacks gelesen werden kann, könnten wir höchstens nach möglichen
            \emph{Endpositionen} des Teilwortes suchen. Sobald wird eine mögliche
            Endposition gefunden haben, haben wir aber bereits den Rest des möglichen
            Treffers überlesen und können nicht mehr entscheiden, ob das Wort in
            der Sprache enthalten ist. \FLASH
    \item   Die Sprache $L_6 = \{ v^R \# w \;|\; v \in \SetB^* \text{ ist Teilwort von } w \in \SetB^* \}$
            ist kontextfrei, da wir einen (nicht-deterministischen) Kellerautomaten bauen können,
            der die Sprache $L_6$ akzeptiert:
            \begin{eqnarray*}
                Q & = & \{q_0,q_1,q_2,q_3\} \\
                \Sigma & = & \SetB \cup \{\#\} \\
                \Gamma & = & \SetB \\
                q_0 & & \text{sei Anfangszustand} \\
                Z_0 & = & \varnothing \\
                F & = & \{q_3\}
            \end{eqnarray*}
            $$ \delta = \begin{cases}
                \quad (q_0, 0, S)  & \rightarrow\quad (q_0, 0S) \\
                \quad (q_0, 1, S)  & \rightarrow\quad (q_0, 1S) \\
                \quad (q_0, \#, S) & \rightarrow\quad (q_1, S) \\
                \quad (q_1, 0, 0S) & \rightarrow\quad (q_2, S) \\
                \quad (q_1, 1, 1S) & \rightarrow\quad (q_2, S) \\
                \quad (q_1, 0, S)  & \rightarrow\quad (q_1, S) \\
                \quad (q_1, 1, S)  & \rightarrow\quad (q_1, S) \\
                \quad (q_2, 0, 0S) & \rightarrow\quad (q_2, S) \\
                \quad (q_2, 1, 1S) & \rightarrow\quad (q_2, S) \\
                \quad (q_2, 0, \varnothing) & \rightarrow\quad (q_3, \varnothing) \\
                \quad (q_2, 1, \varnothing) & \rightarrow\quad (q_3, \varnothing)
            \end{cases} $$
            Die Konstruktion eines (nicht-deterministischen) Kellerautomaten ist
            möglich, da das zu suchende Teilwort in reversierter Reihenfolge
            gelesen wird und durch das Speichern auf dem Stack dann in korrekter
            Reihenfolge vorliegt (LIFO-Prinzip des Stacks).
            
            Im Zustand $q_0$ wird das zu suchende Teilwort auf den Stack übertragen,
            in Zustand $q_1$ werden mögliche Startpositionen für das Teilwort
            gesucht und in Zustand $q_2$ wird ab einer möglichen Startposition
            das Teilwort verglichen. Nach erfolgreichem vollständigen Vergleichen
            des Teilworts (Stack ist leer) wird die Eingabe akzeptiert.
            
            Jede Sprache, für die sich ein Kellerautomat bauen läßt, der diese
            Sprache akzeptiert, ist kontextfrei. Somit ist $L_3$ kontextfrei. \QED
\end{enumerate}

\section*{Aufgabe 3}
\begin{enumerate}[(a)]
    \item   Nein, es gibt \emph{keine} inhärent mehrdeutige \emph{reguläre} Sprachen.
            Man kann jeder Sprache $L$ \emph{genau} eine Äquivalenzrelation $R_L$ zuordnen.
            Gäbe es eine inhärent mehrdeutige \emph{reguläre} Sprache, dann müsste es
            mindestens zwei \emph{verschiedene} Minimalautomaten geben, die die Sprache
            akzeptieren. Jedem dieser Minimalautomaten könnten wir dann \emph{verschiedene}
            Äquivalenzrelationen zuordnen. Dies widerspricht dem Satz, dass man jeder
            Sprache \emph{genau} eine Äquivalenzrelation zuordnen kann. \FLASH            
    \item   Kontextfreie Grammatik für die Menge der regulären Ausdrücke über $\{a,b\}$:
            \begin{eqnarray*}
                S & \rightarrow & S + M \\
                  & \rightarrow & M \\
                M & \rightarrow & M \cdot P \\
                  & \rightarrow & P \\
                P & \rightarrow & A^* \\
                  & \rightarrow & A \\
                A & \rightarrow & \varnothing \\
                  & \rightarrow & \varepsilon \\
                  & \rightarrow & a \\
                  & \rightarrow & b \\
                  & \rightarrow & ( S )
            \end{eqnarray*}
\end{enumerate}

\end{document}
