\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{german}
\usepackage{graphicx}
\usepackage{fullpage}

\newcommand{\ZETTELNUMMER}{5}
\newcommand{\ABGABEDATUM}{am 22. Mai 2015 bis 10 Uhr in die
Tutorenf\"acher}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe~\arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}
\newcommand{\N}{\mathbb{N}}



\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung

\smallskip
\noindent
\large
\textbf{Grundlagen der theoretischen Informatik}\hfill SoSe 2015 \\[0.5ex]
\normalsize
Wolfgang Mulzer

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm


\begin{description}
\AUFGABE{Pumping Lemma}{10 Punkte}

Zeigen Sie, dass die folgenden Sprachen nicht regul\"ar sind.
\begin{enumerate}
\item $\{ 0^n 1 0^{2n} \mid n \in \N \}$,
\item $\{ z^{4^n} \mid n \in \N \}$ und
\item $\{ a^n b^m \mid m,n \in \N, m \neq n \}$.
\end{enumerate}

\AUFGABE{Myhill-Nerode Relation}{10 Punkte}

Bestimmen Sie die \"Aquivalenzklassen der Myhill-Nerode-Relation 
f\"ur die folgenden Sprachen. Geben Sie den Minimalautomaten an, falls 
es sich um eine regul\"are Sprache handelt. Begr\"unden Sie Ihre Antworten.
\begin{align*}
L_1 &= \{ w \in \{0,1\}^* \mid\,\text{$w$ enth\"alt das Teilwort
     $001$}\} \\
L_2 &= \{0^n 1^{3n} \mid\, n \in \N \}.
\end{align*}

\AUFGABE{Verst\"andnisfragen}{10 Punkte}

Welche der folgenden Aussagen treffen zu? Begr\"unden 
Sie Ihre Antwort jeweils in
einem Satz.
\begin{enumerate}
\item Jede Teilmenge von $\Sigma^*$ wird von einem DEA 
  akzeptiert.
\item Jede Teilmenge von $\Sigma^*$ wird von einem NEA 
  akzeptiert.
\item Jede Teilmenge von $\Sigma^*$ wird von einem regul\"aren Ausdruck 
  erzeugt.
\item Jeder DEA akzeptiert eine endliche Teilmenge von
  $\Sigma^*$. 
\item Jede endliche Teilmenge von 
  $\Sigma^*$ wird von einem DEA
  akzeptiert.
\item 
Zu jedem DEA
$M$ gibt es einen
\"aquivalenten NEA,
der nicht
mehr Zust\"ande als $M$ hat. (Zwei Automaten sind 
\emph{\"aquivalent}, wenn sie
die gleiche Sprache akzeptieren.)
\item Das leere Wort wird von jedem NEA akzeptiert.
\item Es gibt einen NEA, der das leere Wort akzeptiert.
\item Die leere Sprache wird von jedem NEA akzeptiert.
\item Wenn es einen NEA gibt, der $L \subseteq \Sigma^*$ akzeptiert, dann
gibt es einen NEA, der $\Sigma^* \setminus L$ akzeptiert.
\end{enumerate}


\AUFGABE{DEAs vs NEAs}{freiwillig, 10 Zusatzpunkte}

Betrachten Sie die folgende Sprache \"uber $\Sigma = \{0,1\}$:
\[
  L = \{ w \in \{0,1\}^* \mid \text{ das viertletzte Zeichen von 
  $w$ ist eine $0$ \}}.
\]
\begin{enumerate}
  \item Geben Sie einen DEA und einen NEA f\"ur $L$ an.
  \item Bestimmen Sie die \"Aquivalenzklassen der 
  Myhill-Nerode-Relation f\"ur $L$.
  \item Was sagen (a) und (b) \"uber den Vergleich zwischen 
  DEAs und NEAs aus?
\end{enumerate}


\end{description}

\end{document}
