\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 12 \\
        Ü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}
$G'=(T,V,S,P')$; $T=\{0,1\}$; $V=\{S,A\}$;
$$P'=\{S \rightarrow 0, A \rightarrow 1, S \rightarrow 1A, S \rightarrow 0SA, A \rightarrow 0S, A \rightarrow 1AS\}$$

\section*{Aufgabe 3}
\subsubsection*{(a)}
\begin{itemize}
\item $aba \in L(M)$:
\begin{eqnarray*}
	(q_0, a, \#) 	& \vdash &	(q_0, b, x \#) \\
			& \vdash &	(q_1, a, x \#) \\
			& \vdash &	(q_1, \varepsilon, \#) \\
			& \vdash &	(q_2, \varepsilon, \varepsilon)
\end{eqnarray*}
\item $abb \in L(M)$:
\begin{eqnarray*}
	(q_0, a, \#)	& \vdash &	(q_0, b, x \#) \\
			& \vdash &	(q_1, b, x \#) \\
			& \vdash &	(q_1, \varepsilon, \#) \\
			& \vdash &	(q_2, \varepsilon, \varepsilon)
\end{eqnarray*}
\item $aa \notin L(M)$:
\begin{eqnarray*}
	(q_0, a, \#)	& \vdash &	(q_0, a, x \#) \\
			& \vdash &	(q_0, \varepsilon, xx \#)
\end{eqnarray*}
Der Kellerautomat hat keine Übergangsfunktion $\delta(q_0, \varepsilon, xx \#)$ und somit ist $aa \notin L(M)$.
\item $bab \notin L(M)$:
\begin{eqnarray*}
	(q_0, b, \#)	& \vdash &	(q_0, a, x \#) \\
			& \vdash &	(q_0, b, xx \#) \\
			& \vdash &	(q_0, \varepsilon, xxx \#) \\ \\
	(q_0, b, \#)	& \vdash &	(q_0, a, x \#) \\
			& \vdash &	(q_0, b, xx \#) \\
			& \vdash &	(q_1, \varepsilon, xx \#) \\ \\
	(q_0, b, \#)	& \vdash &	(q_1, a, \#)
\end{eqnarray*}
Der Kellerautomat hat wegen für $\delta(q_0, \varepsilon, xxx \#)$ noch für $\delta(q_0, b, xx \#)$ noch für $\delta(q_1, a, \#)$ eine Übergangsfunktion.
Somit ist $bab \notin L(M)$.
\end{itemize}

\subsubsection*{(b)}
Die Sprache $L(M)$ muss mit einem $a$ beginnen und mindestens ein $b$ enthalten.

\subsubsection*{(c)}
Konstruiere einen Kellerautomaten $K = (Q, \Sigma, \Gamma, q_0, \#, \delta, F)$ mit $Q = \{q_0, q_1, q_2, q_3\}$, $\Sigma = \{a,b,c\}$, $\Gamma = \{ \#, a\}$
und $F = \{q_3\}$, der die Sprache $\{a^nb^mc^n | n,m \ge 0\}$ akzeptiert:
\begin{eqnarray*}
	\delta(q_0, a, \#)		& = &	\{(q_0, a \#)\} \\
	\delta(q_0, a, a)		& = &	\{(q_0, aa)\} \\
	\delta(q_0, b, a)		& = &	\{(q_1, a)\} \\
	\delta(q_0, b, \#)		& = &	\{(q_2, \#)\} \\
	\delta(q_0, c, a)		& = &	\{(q_2, \varepsilon)\} \\
	\delta(q_1, b, a)		& = &	\{(q_1, a)\} \\
	\delta(q_1, c, a)		& = &	\{(q_2, \varepsilon)\} \\
	\delta(q_2, b, \#)		& =& 	\{(q_2, \#)\} \\
	\delta(q_2, c, a)		& = &	\{(q_2, \varepsilon)\} \\
	\delta(q_2, \varepsilon, \#)	& = &	\{(q_3, \varepsilon)\}
\end{eqnarray*}

\end{document}
