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

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



\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{Regul\"are Ausdr\"ucke I}{10 Punkte}

\begin{enumerate}
  \item
  Geben Sie regul\"are Ausdr\"ucke f\"ur die folgenden Sprachen $L$ 
  \"uber dem Alphabet $\Sigma = \{0, 1\}$ an. 

  \emph{Hinweis}: F\"ur W\"orter mit weniger als drei Buchstaben
  sind die ersten beiden Forderungen trivial erf\"ullt.
  \begin{enumerate}
    \item $L$ enth\"alt alle W\"orter, f\"ur die jeder dritte 
    Buchstabe eine $0$ ist.
    \item $L$ enth\"alt alle W\"orter, deren drittletzter Buchstabe 
        eine $0$ ist.
    \item $L$ enth\"alt genau die Bin\"ardarstellungen
      aller positiven, durch $4$ teilbaren Zahlen.
      Die Zahlen d\"urfen keine f\"uhrenden Nullen 
     haben (d.h., \"uberfl\"ussige Nullen am Anfang sind nicht erlaubt).
     Das leere Wort $\varepsilon$ ist nicht durch vier teilbar.
   \end{enumerate}
    \item
       Beschreiben Sie in deutscher Sprache die 
       durch die folgenden regul\"aren
       Ausdr\"ucke charakterisierten Mengen. 
       Ihre Beschreibungen sollen die Form haben:
       \begin{center}
          \emph{Die Menge aller W\"orter \"uber dem 
	  Alphabet $\{0,1\}$ \dots .``}  %''
        \end{center}
        Dabei soll \dots durch maximal acht W\"orter ersetzt werden. 
        \begin{enumerate}
           \item $(0^* 1 0^* 1 0^*)^*$; und
           \item $(00 \cup 11 \cup (01 \cup 10) 
	   (00 \cup 11)^* (01 \cup 10))^*$.
        \end{enumerate}
\end{enumerate}

\AUFGABE{Regul\"are Ausdr\"ucke II}{10 Punkte}

  Zwei regul\"are Ausdr\"ucke $\alpha, \beta$ 
  hei\ss{}en \emph{\"aquivalent},
  geschrieben $\alpha \sim \beta$, genau dann, wenn sie die gleiche
  Sprache repr\"asentieren, also $L(\alpha)=L(\beta)$ ist.
  Zeigen Sie:
  \begin{enumerate}
    \item $(\alpha \cup \beta)\gamma \sim \alpha\gamma \cup \beta\gamma$;
    \item $(\alpha^*)^* \sim \alpha^*$; 
    \item $(\alpha \cup \beta)^* \sim (\alpha^*\beta^*)^*$;
    \item $\alpha\emptyset \sim \emptyset$; und
    \item $\alpha\emptyset^* \sim \alpha$.
  \end{enumerate}

\AUFGABE{Deterministische endliche Automaten}{10 Punkte}
 
   Geben Sie deterministische endliche Automaten f\"ur die
   folgenden Sprachen \"uber dem Alphabet $\{0,1\}$ an.
   Erkl\"aren Sie Ihren Automaten jeweils in einem Satz.

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

\end{document}
