\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 10 \\
        Ü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 2}
\begin{enumerate}[(a)]
    \item   Wäre die Sprache der korrekten Klammerausdrücke regulär, müsste es
            möglich sein, einen endlichen Automaten zu bauen, der die Sprache
            akzeptiert. Habe der Automat ohne Beschränkung der Allgemeinheit
            $n$ Zustände, so kann bereits das Wort über $(n+1)$ öffnende
            Klammern gefolgt von $(n+1)$ schließenden Klammern nicht mehr
            vom Automaten überprüft werden, obwohl es offensichtlich in der
            Sprache enthalten ist. \FLASH
    \item   Die Grammatik $G$ ist \emph{nicht} eindeutig, da die Regel
            $S \rightarrow SS$ zwei mögliche Ableitungen erlaubt:
            links- oder rechts-assoziativ. Es kann also zum Beispiel bei dem
            Wort \verb\()()()\ nicht unterschieden werden, ob das Wort als
            \verb\AB\ oder \verb\BA\ mit $A \rightarrow ()$ und $B \rightarrow ()()$
            zu interpretieren ist.
            
            Die Sprache der korrekten Klammerausdrücke ist eindeutig, da wir
            eine eindeutige Grammatik für diese Sprache konstruieren können:
            \begin{eqnarray*}
                S & \rightarrow & \varepsilon \\
                S & \rightarrow & L \\
                L & \rightarrow & A \\
                L & \rightarrow & AL \\
                A & \rightarrow & (S)
            \end{eqnarray*}
            Beweis: möge sich der Lesen den Fubbes denken...
    \item   Im folgenden der Algorithmus, der offensichtlich die Entscheidung des
            Wortproblems in linearer Zeit durchführt. \\
            \begin{algorithmic}
                \STATE $c \leftarrow 0$
                \FOR{alle Zeichen $z$ der Eingabe von links nach rechts}
                    \IF{$z = \texttt{'('}$}
                        \STATE $c \leftarrow c + 1$
                    \ELSIF{$z = \texttt{')'}$}
                        \STATE $c \leftarrow c - 1$
                        \IF{$c < 0$}
                            \STATE Wort \emph{nicht} akzeptiert
                        \ENDIF
                    \ELSE
                        \STATE Wort \emph{nicht} akzeptiert
                    \ENDIF
                \ENDFOR
                \IF{$c = 0$}
                    \STATE Wort akzeptiert
                \ELSE
                    \STATE Wort \emph{nicht} akzeptiert
                \ENDIF
            \end{algorithmic}
\end{enumerate}

\newpage
\section*{Aufgabe 3}
\begin{enumerate}[(a)]
    \item   Ursprüngliche Grammatik:
            $$ G=(T,V,S,P),\;T=\{a,b\},\;V=\{S,A,B\} $$
            $$ \begin{array}{rccll}
                P = \{ \quad & S   & \rightarrow & ASA  &, \\
                             & S   & \rightarrow & aB   &, \\
                             & A   & \rightarrow & B    &, \\
                             & B   & \rightarrow & b    &, \\
                             & B   & \rightarrow & \varepsilon & \quad\quad \}
            \end{array} $$
            Grammatik nach Schritt 1:
            $$ G=(T,V,S,P),\;T=\{a,b\},\;V=\{S,A,B,Y_a\} $$
            $$ \begin{array}{rccll}
                P = \{ \quad & S   & \rightarrow & ASA  &, \\
                             & S   & \rightarrow & Y_aB &, \\
                             & Y_a & \rightarrow & a    &, \\
                             & A   & \rightarrow & B    &, \\
                             & B   & \rightarrow & b    &, \\
                             & B   & \rightarrow & \varepsilon & \quad\quad \}
            \end{array} $$            
            Grammatik nach Schritt 2:
            $$ G=(T,V,S,P),\;T=\{a,b\},\;V=\{S,A,B,C_1,Y_a\} $$
            $$ \begin{array}{rccll}
                P = \{ \quad & S   & \rightarrow & AC_1 &, \\
                             & C_1 & \rightarrow & SA   &, \\
                             & S   & \rightarrow & Y_aB &, \\
                             & Y_a & \rightarrow & a    &, \\
                             & A   & \rightarrow & B    &, \\
                             & B   & \rightarrow & b    &, \\
                             & B   & \rightarrow & \varepsilon & \quad\quad \}
            \end{array} $$            
            Grammatik nach Schritt 3:
            $$ G=(T,V,S,P),\;T=\{a,b\},\;V=\{S,A,B,C_1,Y_a\} $$
            $$ \begin{array}{rccll}
                P = \{ \quad & S   & \rightarrow & AC_1 &, \\
                             & S   & \rightarrow & C_1  &, \\
                             & C_1 & \rightarrow & SA   &, \\
                             & C_1 & \rightarrow & S    &, \\
                             & S   & \rightarrow & Y_aB &, \\
                             & S   & \rightarrow & Y_a  &, \\
                             & Y_a & \rightarrow & a    &, \\
                             & A   & \rightarrow & B    &, \\
                             & B   & \rightarrow & b    & \quad\quad \}
            \end{array} $$            
            Grammatik nach Schritt 4:
            $$ G'=(T,V,S,P),\;T=\{a,b\},\;V=\{S,A,B,Y_a\} $$
            $$ \begin{array}{rccll}
                P = \{ \quad & S   & \rightarrow & AS   &, \\
                             & S   & \rightarrow & SA   &, \\
                             & S   & \rightarrow & Y_aB &, \\
                             & S   & \rightarrow & a    &, \\
                             & Y_a & \rightarrow & a    &, \\
                             & A   & \rightarrow & b    &, \\
                             & B   & \rightarrow & b    & \quad\quad \}
            \end{array} $$            
    \item   Nein. Begründung durch Gegenbeispiel: Eine Sprache, die ein Wort
            der Länge 2 enthält, lässt sich nicht darstellen.
\end{enumerate}

\newpage
\section*{Aufgabe 4}
\begin{enumerate}[(a)]
    \item   Tabelle mit $V_{ij}$
            $$
                \begin{array}{c|c|c|c|c|c|c|c|c|c|c}
                    \mathbf{V_{ij}} & \mathbf{1} & \mathbf{0} & \mathbf{1} & \mathbf{0} & \mathbf{1} & \mathbf{1} & \mathbf{0} & \mathbf{1} & \mathbf{0} & \mathbf{0} \\ \hline
                    \mathbf{1}  & C & A & - & A & - & - & - & - & - & A \\ \hline
                    \mathbf{2}  &   & D & - & - & - & - & - & - & - & - \\ \hline
                    \mathbf{3}  &   &   & C & A & - & - & - & - & - & A \\ \hline
                    \mathbf{4}  &   &   &   & D & - & - & - & - & - & - \\ \hline
                    \mathbf{5}  &   &   &   &   & C & - & - & - & - & A \\ \hline
                    \mathbf{6}  &   &   &   &   &   & C & A & - & A & B \\ \hline
                    \mathbf{7}  &   &   &   &   &   &   & D & - & - & - \\ \hline
                    \mathbf{8}  &   &   &   &   &   &   &   & C & A & B \\ \hline
                    \mathbf{9}  &   &   &   &   &   &   &   &   & D & - \\ \hline
                    \mathbf{10} &   &   &   &   &   &   &   &   &   & D
                \end{array}
            $$
            Das Wort $ w = 1010110100 $ ist in der Sprache $L(G)$ enthalten.
            
            \noindent Linksableitung für $ w = 1010110100 $ \\
            (Syntaxbaum siehe Abbildung~\ref{fig:syntaxbaumlinks}):
            \begin{figure}[p]
                \begin{center}
                    \includegraphics[width=.8\textwidth]{info3_10_aufg4al}
                \end{center}
                \caption{Aufgabe 4a: Syntaxbaum für Linksableitung}
                \label{fig:syntaxbaumlinks}
            \end{figure}
            \begin{eqnarray*}
                A & \rightarrow & AA \\
                  & \rightarrow & (AA)A \\
                  & \rightarrow & ((CD)A)A \\
                  & \rightarrow & ((1D)A)A \\
                  & \rightarrow & ((10)A)A \\
                  & \rightarrow & ((10)(CD))A \\
                  & \rightarrow & ((10)(1D))A \\
                  & \rightarrow & ((10)(10))A \\
                  & \rightarrow & ((10)(10))(CB) \\
                  & \rightarrow & ((10)(10))(1B) \\
                  & \rightarrow & ((10)(10))(1(AD)) \\
                  & \rightarrow & ((10)(10))(1((AA)D)) \\
                  & \rightarrow & ((10)(10))(1(((CD)A)D)) \\
                  & \rightarrow & ((10)(10))(1(((1D)A)D)) \\
                  & \rightarrow & ((10)(10))(1(((10)A)D)) \\
                  & \rightarrow & ((10)(10))(1(((10)(CD))D)) \\
                  & \rightarrow & ((10)(10))(1(((10)(1D))D)) \\
                  & \rightarrow & ((10)(10))(1(((10)(10))D)) \\
                  & \rightarrow & ((10)(10))(1(((10)(10))0))
            \end{eqnarray*}
            
            \newpage
            \noindent Rechtsableitung für $ w = 1010110100 $ \\
            (Syntaxbaum siehe Abbildung~\ref{fig:syntaxbaumrechts}):
            \begin{figure}[p]
                \begin{center}
                    \includegraphics[width=.8\textwidth]{info3_10_aufg4ar}
                \end{center}
                \caption{Aufgabe 4a: Syntaxbaum für Rechtsableitung}
                \label{fig:syntaxbaumrechts}
            \end{figure}
            \begin{eqnarray*}
                A & \rightarrow & AA \\
                  & \rightarrow & (CD)A \\
                  & \rightarrow & (1D)A \\
                  & \rightarrow & (10)A \\
                  & \rightarrow & (10)(AA) \\
                  & \rightarrow & (10)((CD)A) \\
                  & \rightarrow & (10)((1D)A) \\
                  & \rightarrow & (10)((10)A) \\
                  & \rightarrow & (10)((10)(CB)) \\
                  & \rightarrow & (10)((10)(1B)) \\
                  & \rightarrow & (10)((10)(1(AD))) \\
                  & \rightarrow & (10)((10)(1((AA)D))) \\
                  & \rightarrow & (10)((10)(1(((CD)A)D))) \\
                  & \rightarrow & (10)((10)(1(((1D)A)D))) \\
                  & \rightarrow & (10)((10)(1(((10)A)D))) \\
                  & \rightarrow & (10)((10)(1(((10)(CD))D))) \\
                  & \rightarrow & (10)((10)(1(((10)(1D))D))) \\
                  & \rightarrow & (10)((10)(1(((10)(10))D))) \\
                  & \rightarrow & (10)((10)(1(((10)(10))0))) \\
            \end{eqnarray*}
    \item   Tabelle mit $V_{ij}$
            $$
                \begin{array}{c|c|c|c|c|c|c}
                    \mathbf{V_{ij}} & \mathbf{1} & \mathbf{1} & \mathbf{0} & \mathbf{0} & \mathbf{0} & \mathbf{1} \\ \hline
                    \mathbf{1} & C & - & - & A & B & - \\ \hline
                    \mathbf{2} &   & C & A & B & - & - \\ \hline
                    \mathbf{3} &   &   & D & - & - & - \\ \hline
                    \mathbf{4} &   &   &   & D & - & - \\ \hline
                    \mathbf{5} &   &   &   &   & D & - \\ \hline
                    \mathbf{6} &   &   &   &   &   & C
                \end{array}
            $$
            Das Wort $ w = 110001 $ ist \emph{nicht} in der Sprache $L(G)$ enthalten.
\end{enumerate}

\end{document}
