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

\newcommand{\ZETTELNUMMER}{7}
\newcommand{\ABGABEDATUM}{am 8. Juni 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{Mehrband-Turingmaschinen}{10 Punkte}

Eine \emph{Mehrband-Turingmaschine} ist eine Turingmaschine,
die \"uber $k$ Arbeitsb\"ander verf\"ugt, die jeweils einen
unabh\"angigen Schreib-/Lesekopf haben. Hierbei ist $k \geq 2$ 
eine Konstante.

\begin{enumerate}
\item  Geben Sie eine geeignete Definition f\"ur eine 
Mehrband-Turingmaschine. Wie muss die 
\"Uberf\"uhrungsfunktion aussehen?

\item Begr\"unden Sie, dass Ihre Mehrband-Turingmaschine 
von der Turingmaschine aus der Vorlesung simuliert 
werden kann.

\emph{Hinweis}: Arbeiten Sie mit einem erweiterten 
Bandalphabet. F\"uhren Sie $2k$ Spuren auf dem Band ein, 
wobei die ersten $k$ Spuren den Bandinhalt und die 
zweiten $k$ Spuren die Kopfpositionen der Mehrband-TM 
kodieren.  Simulieren Sie einen Schritt der Mehrband-TM 
durch konstant viele Scans der Einband-TM \"uber das ganze 
Band.
\end{enumerate}

\AUFGABE{Kodierte DEAs}{10 Punkte}

Zeigen Sie, dass die beiden folgenden Sprachen entscheidbar 
sind. Dabei sei $\langle M \rangle$ eine geeignete Kodierung 
eines endlichen Automaten $M$. (Machen Sie sich klar, wie
diese Kodierung aussehen k\"onnte!)
\begin{enumerate} 
\item $L_\infty = \{ \langle M \rangle \mid \text{$M$ ist 
          ein DEA und $L(M)$ ist unendlich.} \}$; und
\item $L = \{\langle M \rangle \mid \text{$M$ ist ein DEA 
und akzeptiert $\Sigma^*$.} \}$.
\end{enumerate}
 
\AUFGABE{Entscheidbarkeit}{10 Punkte}

Welche der folgenden Aussagen sind wahr? Geben Sie jeweils 
einen Beweis oder ein Gegenbeispiel an. 
\begin{enumerate}
\item Jede Sprache \"uber dem Alphabet $\Sigma = \{1\}$ ist 
entscheidbar.
\item Wenn $L_1$ und $L_2$ entscheidbar sind, dann ist auch 
$L_1L_2$ entscheidbar.
\item  Wenn $L$ unentscheidbar ist, dann ist auch $L^*$ 
unentscheidbar.
\item Wenn $L$ entscheidbar ist, dann ist auch $L^*$ 
entscheidbar.
\end{enumerate}

\end{description}
\end{document}
