\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 25. Mai 2018 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 2018 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Katharina Klost

\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 $\{ a^n b a^n \mid n \in \N \}$,
\item $\{ a^{2^n} \mid n \in \N \}$ und
\item $\{ a^n b^m \mid m,n \in \N, m \neq n \}$.
\end{enumerate}

%\AUFGABE{Minimalautomat}{10 Punkte}
%
%Minimieren Sie den folgenden endlichen Automaten mit dem Algorithmus aus der
%Vorlesung.
%
%\begin{center}
%  \includegraphics[width=0.6\textwidth]{u05automat}
%\end{center}
%
% Welche Sprache wird akzeptiert? 


\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{die Anzahl der $0$en und $1$en in 
   jedem Pr\"afix von $w$} \\ 
   &\phantom{= \{ w \in \{0,1\}^* \mid\,} 
     \text{ unterscheidet sich um h\"ochstens $1$}  \},\\
L_2 &= \{0^n 1^{2n} \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 endliche Teilmenge von $\Sigma^*$ wird von einem endlichen Automaten
  akzeptiert.
\item Ein endlicher Automat kann nur endlich viele W\"orter akzeptieren.
\item Jede Teilmenge von $\Sigma^*$ wird von einem endlichen Automaten
  akzeptiert.
\item 
Zu jedem deterministischen endlichen Automaten
$A$ gibt es einen
\"aquivalenten nichtdeterministischen endlichen Automaten,
der nicht
mehr Zust\"ande als $A$ hat. (Zwei Automaten sind \emph{\"aquivalent}, wenn sie
die gleiche Sprache akzeptieren.)
\item Die leere Sprache wird von jedem endlichen Automaten 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 $1$ \}}.
\]
\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}
