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

\newcommand{\ZETTELNUMMER}{4}
\newcommand{\ABGABEDATUM}{am 15. Mai 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}}



\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{Algorithmus von Kleene}{10 Punkte}

\begin{enumerate}
\item
  Konstruieren Sie mit dem Algorithmus von Kleene einen 
  regul\"aren Ausdruck zu folgendem endlichen Automaten. 
  \begin{center}
    \includegraphics[width=0.4\textwidth]{u04automat}
   \end{center}
   Dabei d\"urfen Sie die Zwischenausdr\"ucke $R_{ij}^{(k)}$ 
   vereinfachen.  
   Beschreiben Sie die akzeptierte Sprache in einem Satz. 
\item 
  Geben Sie eine m\"oglichst gute untere Schranke f\"ur die 
  L\"ange des regul\"aren Ausdrucks, den man erh\"alt, wenn 
  man den Algorithmus von Kleene auf einen NEA mit $n$ 
  Zust\"anden anwendet, ohne die Zwischenausdr\"ucke zu vereinfachen.
\end{enumerate}


\AUFGABE{Schnitt von regul\"aren Sprachen}{10 Punkte}
 
Aus der Vorlesung wissen Sie: Wenn $L_1$ und $L_2$ regul\"are
Sprachen sind, so ist auch $L_1 \cap L_2$ regul\"ar.
Hier wollen wir diese Tatsache mit Hilfe einer
direkten Konstruktion beweisen. 

Seien  $M_1 = \bigl(\Sigma, Q_1, q_0^{(1)}, F_1, \delta_1\bigr)$ und
$M_2 = \bigl(\Sigma, Q_2, q_0^{(2)}, F_2, \delta_2\bigr)$ deterministische
endliche Automaten mit $L(M_1) = L_1$ und $L(M_2) = L_2$.
Geben Sie einen DEA mit Zustandsmenge
$Q_1 \times Q_2$ an, der die Sprache $L_1 \cap L_2$ erkennt.
Beweisen Sie die Korrektheit Ihres Automaten.

\emph{Hinweis}: Der neue Automat simuliert die Automaten
$M_1$ und $M_2$ gleichzeitig.

\AUFGABE{Operationen auf DEAs}{10 Punkte}

Sei $M$ ein DEA. Skizzieren Sie die notwendigen
Schritte, um einen DEA f\"ur
\begin{enumerate}
\item die Komplement\"arsprache $\Sigma^* \setminus L(M)$ und
\item die gespiegelte Sprache $L(M)^R = \{ w^R \mid w \in L(M) \}$
\end{enumerate}
f\"ur M zu konstruieren.  Dabei ist $w^R$ das Wort, das man erh\"alt,
indem man das Wort $w$ von hinten liest.

\AUFGABE{Halbe Sprache}{freiwillig, 10 Zusatzpunkte}

Sei $L \subseteq \{0,1\}^*$. Wir definieren $L_{1/2^-}$ als die
Sprache, die aus den ersten H\"alften der W\"orter aus $L$ besteht, d.h.,
\[
L_{1/2^-} :=  \{x \mid \exists y, \text{so dass } |x| = |y| \text{ und }
  xy \in L\}.
\]
Zeigen Sie: Ist $L$ regul\"ar, so auch
$L_{1/2^-}$.

\end{description}

\end{document}
