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

\newcommand{\ZETTELNUMMER}{3}
\newcommand{\ABGABEDATUM}{am 11. 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}}



\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{Deterministische endliche Automaten}{10 Punkte}
 
   Geben Sie deterministische endliche Automaten f\"ur die
   folgenden Sprachen \"uber dem Alphabet $\{0,1\}$.
   Erkl\"aren Sie Ihren Automaten jeweils in einem Satz.

   \begin{enumerate}
      \item Die Menge aller W\"orter, deren erster und letzter 
      Buchstabe gleich
        sind.
      \item Die Menge aller W\"orter, deren vorletzer Buchstabe eine $1$ 
      ist.
      \item Die Menge aller W\"orter, die $0110$ als Teilwort enthalten.
      \item Die Menge aller durch drei teilbaren Zahlen (in 
      Bin\"ardarstellung).
        Das leere Wort $\varepsilon$ ist nicht durch drei teilbar.
   \end{enumerate}


\AUFGABE{Potenzmengenkonstruktion}{10 Punkte}

Betrachten Sie den nichtdeterministischen endlichen Automaten $M$ mit
 $\Sigma=\{0,1\}$, $Q=\{a,b,c\}$,
 $q_0=a$, $F = \{a\}$ und
%\delta=\{(a,0,a),(a,0,b),(b,1,b),(b,1,c),(c,0,c),(c,0,a)
$\delta(a,0)=\{a,b\}$,
$\delta(b,1)=\{b,c\}$,
$\delta(c,0)=\{a,c\}$,
$\delta(a,1)=
\delta(b,0)=
\delta(c,1)=\emptyset$.
\begin{enumerate}
  \item Zeichnen Sie das Zustandsdiagramm f\"ur $M$.
  \item Benutzen Sie die Potenzmengenkonstruktion, um 
    einen zu $M$ \"aquivalenten deterministischen endlichen
    Automaten zu finden. Beseitigen Sie alle \"uberfl\"ussigen
    Zust\"ande. 
\end{enumerate}

\AUFGABE{NEAs mit mehreren Startzust\"anden}{10 Punkte}

In der Vorlesung haben wir definiert, dass nichtdeterministische
endliche Automaten genau einen Startzustand besitzen. In dieser
Aufgabe wollen wir die Variante betrachten, dass es \emph{mehrere}
Startzust\"ande geben kann.

\begin{enumerate}
  \item Geben Sie eine sinnvolle Definition f\"ur nichtdeterministische
    endliche Automaten mit mehreren Startzust\"anden. Erkl\"aren Sie insbesondere,
    wie die Sprache definiert ist, die von einem solchen Automaten erkannt wird.
  \item Sei $L \subseteq \Sigma^*$ eine Sprache. Zeigen Sie: 
    Es existiert ein NEA mit genau einem Startzustand, der $L$ akzeptiert,
    genau dann, wenn es einen NEA mit mehreren Startzust\"anden gibt,
    der $L$ akzeptiert.
\end{enumerate}

\end{description}
\end{document}
