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

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

\noindent
Dies ist das 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 = \{a, b\}$ und
  $L = \{\overline{w}w \mid w \in \{a,b\}^*\}$, wobei
    $\overline{w}$ aus $w$ hervor geht, indem man
    jedes $a$ durch ein $b$ und jedes $b$ durch ein $a$ ersetzt.
\item $\Sigma = \{0,1\}$ und $L = \{0^n 1^{2^n} \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{Verst\"andnisfragen}{10 Punkte}

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 Es gibt eine kontextfreie Sprache mit endlich vielen W\"ortern.
\item Der Schnitt zweier kontextfreier Sprachen ist wieder kontextfrei.
\item Wenn eine Sprache regul\"ar ist, dann ist sie auch kontextsensitiv.
\item Die folgende Sprache kann durch eine Grammatik erzeugt werden:
  \[
    \{ \langle M \rangle \mid \text{Der DEA $M$ erkennt die Sprache
      $\{0,1\}^*$.} \}.
  \]
\end{enumerate}

\AUFGABE{Typ-3 Sprachen und regul\"are Sprachen}{freiwillig, 
10 Zusatzpunkte}

\begin{enumerate}
\item  Sei $M = (\Sigma, Q, q_0, F, \delta)$ ein DEA
 mit $\varepsilon \not\in L(M)$. 
Geben Sie eine Grammatik $G$ vom Typ 3 an, so
dass $L(G) = L(M)$ ist. Begr\"unden Sie die Korrektheit.

\emph{Hinweis}: W\"ahlen Sie $V = Q$ und $S = q_0$. 
Wie sehen die Produktionen aus?

\item  Sei $G = (V, \Sigma, S, P)$ eine Grammatik vom Typ 3 mit
$\varepsilon \not\in L(G)$. Geben Sie
  einen nichtdeterministischen endlichen Automaten $M$ an, so dass
  $L(G) = L(M)$ ist. Begr\"unden Sie die Korrektheit.

\emph{Hinweis}: W\"ahlen Sie $Q = V \cup \{X\}$, wobei $X$ ein neuer 
Zustand ist, der nicht in $V$ vorkommt, und setzen Sie $F = \{X\}$. 
Wie muss man die
\"Uberg\"ange und den Startzustand w\"ahlen?


\item Folgern Sie, dass die Typ-3-Sprachen genau die 
regul\"aren Sprachen sind.
\end{enumerate}



\end{description}

\end{document}
