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

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

\noindent
Dies ist das \emph{letzte} Aufgabenblatt.
\vskip 0.5cm


\begin{description}

\AUFGABE{Der CYK-Algorithmus}{10 Punkte}

Gegeben sei die folgende Grammatik \"uber dem
Alphabet $\Sigma = \{a,b\}$.
\[
S \to AB \ | \ BC, A \to BA \ | \ a, B \to CC \ | \ b, C \to AB \ | \ a.
\]
Wenden Sie den CYK-Algorithmus an auf die W\"orter
$w_1 = aaaaa$, $w_2 = aaaaaa$ und $w_3 = baaba$.
Zeichnen Sie gegebenenfalls auch einen zugeh\"origen Syntaxbaum.


\AUFGABE{Pumping-Lemma}{10 Punkte}

Zeigen Sie, dass die folgenden Sprachen nicht kontextfrei sind.
\begin{enumerate}
\item $\Sigma = \{0, 1\}$ und
  $L = \{w\overline{w} \mid w \in \Sigma^*\}$, wobei
    $\overline{w}$ aus $w$ hervor geht, indem man
    jede $0$ durch eine $1$ und jede $1$ durch eine $0$ ersetzt.
\item $\Sigma = \{0,1\}$ und $L = \{0^n 1^{n^2} \mid  n \in \N\}$.
\item $\Sigma = \{a,b,c\}$ und $L = \{a^m b^n c^{mn} \mid m,n \in \N\}$.
\end{enumerate}

\AUFGABE{Chomsky Normalform}{10 Punkte}

\begin{enumerate}
  \item Sei $G$ eine kontextfreie Grammatik in 
  Chomsky Normalform, und sei $w \in L(G)$
  mit $n := |w| \geq 1$. Zeigen Sie, dass jede Ableitung von $w$ genau
  $2n-1$ Schritte besitzt. 

  \emph{Hinweis}: Betrachten Sie den zugeh\"origen Syntaxbaum.

  \item Sei $G$ eine kontextfreie Grammatik in Chomsky Normalform mit $b$ Variablen.
    Zeigen Sie: Wenn ein Wort $w \in L(G)$ existiert, so dass eine Ableitung von
    $w$ mindestens $2^b$ Schritte ben\"otigt, so ist $L(G)$ unendlich.

  \emph{Hinweis}: Gehen Sie vor wie im Beweis des Pumping-Lemmas.
\end{enumerate}

\newpage 

\AUFGABE{Verst\"andnisfragen}{freiwillig, 10 Zusatzpunkte}

Welche der folgenden Aussagen treffen zu? Begr\"unden Sie Ihre Antwort jeweils in
einem Satz.

\begin{enumerate}
\item Jede Sprache $L \subseteq \{0,1\}^*$ kann durch eine Grammatik erzeugt werden.
\item Jede kontextfreie Sprache hat unendlich viele W\"orter.
\item Die Vereinigung zweier kontextfreier Sprachen ist wieder kontextfrei.
\item Wenn eine Sprache kontextsensitiv ist, dann ist sie auch regul\"ar.
\item Die folgende Sprache kann durch eine Grammatik erzeugt werden:
  \[
    \{ \langle M \rangle \mid \text{Die Turingmaschine $M$ h\"alt nach
      h\"ochstens $16534$ Schritten}\}.
  \]
\end{enumerate}

\end{description}

\end{document}
