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

\newcommand{\ZETTELNUMMER}{6}
\newcommand{\ABGABEDATUM}{am 29. 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{Minimalautomat}{10 Punkte}

Minimieren Sie den folgenden endlichen Automaten mit dem Algorithmus aus der
Vorlesung und geben Sie den Minimalautomaten an.

\begin{center}
  \includegraphics[width=0.6\textwidth]{u06automat}
\end{center}

 Welche Sprache wird akzeptiert? 

\AUFGABE{Turing-Maschinenprogrammierung}{10 Punkte}
 
Geben Sie eine Turing-Maschine an, welche die Sprache
\[
L = \{ w\,\text{\euro}\,\overline{w} \mid w \in \{a,b\}^*\}
\]
\"uber dem Eingabealphabet $\Sigma = \{a,b,\text{\euro}\}$ erkennt. 
Dabei ist $\overline{w}$ das Wort, das aus $w$ entsteht, indem man
$a$ durch $b$ und $b$ durch $a$ ersetzt.
Beschreiben Sie Ihre Maschine in Worten und formal durch Angabe der
\"Uberf\"uhrungsfunktion.

\noindent
\emph{Hinweis}: F\"uhren Sie zus\"atzliche Zeichen im Bandalphabet ein,
um Markierungen auf dem Band darzustellen.

\AUFGABE{Simulation}{10 Punkte}

\begin{enumerate}
  \item Beschreiben Sie, wie man einen DEA durch eine 
    Turing-Maschine simulieren kann. Sch\"atzen Sie die
    Anzahl der Schritte ab, die ihre Simulation ben\"otigt.
    Begr\"unden Sie Ihre Antwort.
  \item Wir \"andern die Definition von Turing-Maschinen, so dass
  die \"Uberf\"uhrungsfunktion die Form $\delta : Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}$
  hat. Das hei\ss{}t, die M\"oglichkeit, den Kopf nicht zu bewegen, besteht nicht mehr.
  Zeigen Sie, dass dies \"aquivalent zur Definition aus der Vorlesung ist.
\end{enumerate}


\AUFGABE{JFlex}{freiwillig, 10 Zusatzpunkte}
 
In der Vorlesung wurden Scanner-Generatoren erw\"ahnt,
die beim \"Ubersetzerbau zum Einsatz kommen. Ein solcher
Scanner-Generator hei\ss{}t \emph{JFlex}. 

\begin{enumerate}
\item
Auf der Veranstaltungsseite befindet sich das Beispielprogramm
\texttt{summe.flex}. Laden Sie das Programm herunter und
finden Sie mit Hilfe der Dokumentation von JFlex heraus, wie 
man es ausf\"uhrt. F\"uhren Sie einige
Testl\"aufe durch und dokumentieren Sie diese. Gehen Sie dann
den Quelltext von \texttt{summe.flex} durch und erkl\"aren Sie, was
die einzelnen Anweisungen bedeuten.
\item
Bearbeiten Sie eine der beiden folgenden Aufgaben:
\begin{enumerate}
\item Ermitteln Sie, wie der Algorithmus funktioniert, der
Scanner-Generatoren zu Grunde liegt (z.B.~aus dem Buch von I.~Wegener). Erl\"autern
Sie diesen Algorithmus kurz in zwei Abs\"atzen. Erkl\"aren Sie auch den
Zusammenhang zum Vorlesungsstoff.
\item
Modifizieren Sie \texttt{summe.flex} so, dass
bei Eingabe des Zeichens \texttt{*} 
die n\"achste Zahl nicht addiert, sondern multipliziert
wird.  Bei Eingabe von
\texttt{=} soll das bisherige Ergebnis ausgedruckt werden.
Au\ss{}erdem sollen Kommentare im Stil von Python unterst\"utzt werden:
alles zwischen \texttt{\%} und dem Ende der Zeile wird ignoriert.
\end{enumerate}
\end{enumerate}


\end{description}

\end{document}
