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

\newcommand{\ZETTELNUMMER}{9}
\newcommand{\ABGABEDATUM}{am 20. Juni 2014 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 2014 \\[0.5ex]
\normalsize
Wolfgang Mulzer

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm


\begin{description}

\AUFGABE{Reduktionen}{10 Punkte}

\begin{enumerate}
\item Sei $H_0 := \{ \langle M \rangle \mid M \text{ h\"alt bei Eingabe 
$\varepsilon$}\}$. Zeigen Sie: $H \leq H_0$.
\item Seien $X$ und $R$ Sprachen, so dass $R$ regul\"ar ist und
$X \leq R$ gilt. Muss $X$ dann ebenfalls regul\"ar sein?
Begr\"unden Sie Ihre Antwort.
\item Sei $D$ die Diagonalsprache und $U$ die Universalsprache.
  Zeigen Sie, dass es keine Reduktion von $D$ auf $U$ geben kann.

\emph{Hinweis}: Zeigen Sie, dass $D$ sonst entscheidbar w\"are.
\end{enumerate}

\AUFGABE{Grammatiken I}{10 Punkte}

  Geben Sie kontextfreie Grammatiken f\"ur die folgenden Sprachen an.
  Begr\"unden Sie jeweils die Korrektheit Ihrer Grammatik.

\begin{enumerate}
  \item Die Menge aller Palindrome \"uber dem Alphabet $\{0,1\}$.
  \item Die Sprache $\{ 0^n 1 0^n \mid n \in \N\}$ \"uber dem Alphabet
    $\Sigma = \{0,1\}$.
  \item Die Sprache $L = \{a^n b^m \mid n \neq m\}$ \"uber dem Alphabet 
    $\Sigma = \{a,b\}$.
  \item Die Menge aller W\"orter, die doppelt so viele $1$'en wie $0$'en
    enthalten, \"uber dem Alphabet $\Sigma = \{0,1\}$.
\end{enumerate}


\AUFGABE{Grammatiken II}{10 Punkte}

Zeigen Sie, dass die Grammatik $G$ mit den Regeln
$S \rightarrow aS \mid SS \mid aSbS \mid \varepsilon$ genau
die W\"orter \"uber $\Sigma = \{a, b\}$ erzeugt, in denen jeder
Pr\"afix mindestens so viele $a$'s wie $b$'s enth\"alt.




\AUFGABE{Rekursiv aufz\"ahlbare Sprachen}{freiwillig, 10 Zusatzpunkte}

Beweisen Sie: Eine Sprache $L$ ist genau dann
rekursiv aufz\"ahlbar, wenn es eine Turingmaschine $M$ gibt, die
alle W\"orter von $L$ (in beliebiger Reihenfolge) durch Leerzeichen
getrennt auf ein Ausgabeband ausgibt, auf das nur geschrieben werden kann.

\emph{Hinweis}: Sie m\"ussen alle W\"orter $w \in \Sigma^*$ aufz\"ahlen und jeweils
  \"uberpr\"ufen, ob $w$ in $L$ enthalten ist. Wie k\"onnen Sie dies bewerkstelligen,
  ohne dass ein Problem entsteht, wenn die Turingmaschine f\"ur $L$ nicht anh\"alt?

\end{description}
\end{document}
