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

\newcommand{\ZETTELNUMMER}{10}
\newcommand{\ABGABEDATUM}{am 29. 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{Typ-3 und regul\"are Sprachen}{10 Punkte}

\begin{enumerate}
\item  Sei $M = (\Sigma, Q, q_0, F, \delta)$ ein deterministischer
endlicher Automat, so dass $\varepsilon \not\in L(M)$ ist. 
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 m\"ussen die Produktionen aussehen?
\item  Sei $G = (V, \Sigma, S, P)$ eine Grammatik vom Typ 3, so dass
$\varepsilon \not\in L(G)$ ist. 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}

\AUFGABE{Grammatiken und der Kleene-Stern}{10 Punkte}

\begin{enumerate}
\item Die folgende Konstruktion soll zeigen, dass kontextfreie Sprachen
  unter dem Kleene-Stern abgeschlossen sind: Sei $G = (V,\Sigma, S, P)$
  eine kontextfreie Grammatik.
  F\"uge zu $G$ die Ableitung
  $S \rightarrow SS$ hinzu und nenne die resultierende Grammatik $G'$. 
  Behauptung: $L(G') = L(G)^*$.

  Zeigen Sie durch ein Gegenbeispiel, dass die obige Konstruktion im
  Allgemeinen nicht korrekt ist.

\item  Geben Sie eine korrekte Konstruktion f\"ur das Problem aus
  (a) an und begr\"unden Sie die Korrektheit.
\end{enumerate}

\AUFGABE{Chomsky-Normalform}{10 Punkte}

Wandeln Sie die folgende Grammatik \"uber
dem Terminalalphabet $\Sigma=\{0,1\}$ in Chomsky-Normalform um.
\[
\begin{array}{ll}
S\to 0A0 \ | \ 1B1 \ | \ BB
\qquad
&
B\to S \ | \ A
\\[1pt]
A\to C
&
C\to S\ |\ \varepsilon
\end{array}
\]

\AUFGABE{Dangling Else}{freiwillig, 10 Zusatzpunkte}

Die Grammatik
\[
\begin{array}{l}
S\to \textbf{if } (B)\ S \ \bigm|\ \textbf{if } (B)\ S \textbf{ else } S
\ \bigm| \  \textrm{print}(0); 
\ \bigm| \  \textrm{print}(1);
\ \bigm| \  \textrm{print}(2); \\
B \to \textrm{T}\ \bigm| \  \textrm{F}
\end{array}
\]
ist mehrdeutig, wie das Beispiel
\[\textrm{\textbf{if} (T) \textbf{if} (F) \textbf{if} (F) print(0); \textbf{else}
\textbf{if} (T) print(0); \textbf{else} print(1); \textbf{else}
  print(2);}\]
zeigt.
Die Mehrdeutigkeit kann durch die g\"angige Regel aufgel\"ost werden, dass eine
\textbf{else}-Klausel immer dem \emph{letzten} \textbf{if} zugeordnet wird, dem
noch keine \textbf{else}-Klausel zugeordnet wurde.
Nach dieser Regel w\"urde der obige Ausdruck 2 drucken,
wenn man ihn als Programm auffasst. 
Geben Sie eine eindeutige Grammatik an, die dieser Regel entspricht.

\end{description}
\end{document}
