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

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

Sei $k \geq 2$ eine Konstante.
Eine \emph{Mehrband-Turingmaschine} ist eine Turingmaschine
mit $k$ Arbeitsb\"andern, die jeweils einen
unabh\"angigen Schreib-/Lesekopf haben. 

\begin{enumerate}
  \item  Geben Sie eine geeignete Definition f\"ur eine Mehrband-Turingmaschine.
    Wie muss die \"Uberf\"uhrungsfunktion aussehen?
  \item Beweisen Sie, dass Ihre Mehrband-Turingmaschine von der 
    Turingmaschine aus der Vorlesung simuliert werden kann.

  \emph{Hinweis}: Arbeiten Sie mit einem erweiterten Bandalphabet.
    Eine Zelle des Bandes speichert ein \emph{$2k$-Tupel}
    von Zeichen.
    Dabei kodieren die ersten
    $k$ Elemente den Inhalt der B\"ander und die zweiten $k$ Elemente die Kopfpositionen
    der Mehrband-TM.
    Simulieren Sie einen Schritt der Mehrband-TM durch konstant viele Scans der
    Einband-TM \"uber das ganze beschriebene Band.

\end{enumerate}

\AUFGABE{Kodierte DEAs}{10 Punkte}

Zeigen Sie, dass die 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!) Es sei jeweils $\Sigma = \{0,1\}$.
\begin{enumerate} 
\item $L = \{ \langle M \rangle \mid \text{$M$ ist ein DEA und $L(M)$ ist endlich.} \}$; und
\item $L = \{\langle M \rangle \mid \text{$M$ ist ein DEA  und akzeptiert $L(0^*1^*)$.} \}$.
\end{enumerate}
 

\AUFGABE{Entscheidbarkeit}{10 Punkte}

Welche der folgenden Aussagen sind wahr? Begr\"unden Sie jeweils Ihre Antwort.
\begin{enumerate}
  \item Jede Sprache \"uber dem Alphabet $\Sigma = \{a\}$ ist entscheidbar.
  \item Wenn $L$ entscheidbar ist, dann ist auch $L^*$ entscheidbar.
  \item  Wenn $L$ unentscheidbar ist, dann ist auch $L^*$ unentscheidbar.
   \item Wenn $L$ entscheidbar ist und $w \in \Sigma^*$ ist, dann ist auch $L \cup \{w\}$ entscheidbar.
\end{enumerate}

\end{description}

\end{document}
