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

\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]
Probeklausur zur Vorlesung

\smallskip
\noindent
\large
\textbf{Grundlagen der theoretischen Informatik} \hfill SoSe 2015\\[0.5ex]
\normalsize
Wolfgang Mulzer

\medskip\hrule
\smallskip
\noindent
Bearbeitungszeit: mindestens 90 Minuten 

\vskip 0.5cm

\begin{description}

%\newpage
\AUFGABE{Endliche Automaten}{3+3+4 Punkte}

\begin{enumerate}
  \item Betrachten Sie den folgenden nichtdeterministischen endlichen
    Automaten $M$. 
    Benutzen Sie die Potenzmengenkonstruktion, um einen
    deterministischen endlichen Automaten $M'$ mit $L(M') = L(M)$
    zu finden. Lassen Sie dabei keine Zust\"ande weg.
     \begin{center}
      \includegraphics{potenzAutomat}
     \end{center}
  \item Geben Sie einen deterministischen endlichen
    Automaten mit vier Zust\"anden, der die folgende Sprache
    \"uber $\Sigma = \{a,b\}$ erkennt:
    \[
      L = \{w \mid \text{der vorletzte Buchstabe von $w$ ist ein $a$}\}.
    \]
   Beachten Sie: Die Bedingung gilt f\"ur alle W\"orter mit
   weniger als zwei Zeichen.
   \item Sei $L$ die Sprache aus (b). Gibt es einen deterministischen
     endlichen Automaten $M$ 
     mit drei Zust\"anden, so dass $L(M) = L$ ist?
     Geben Sie einen solchen Automaten an
     oder beweisen Sie, dass er nicht existieren kann.
\end{enumerate}

\AUFGABE{Klassifizierung von Sprachen}{6+4 Punkte}

Entscheiden Sie f\"ur die beiden 
folgenden Sprachen, ob sie jeweils 
regul\"ar, kontextfrei, entscheidbar 
oder semientscheidbar sind.

Geben Sie bei einer positiven 
Antwort eine(n) geeignete(n) 
Grammatik, Turing-Maschine, 
Reduktion, Automaten oder 
\"ahnliches an. F\"uhren Sie 
im Falle einer negativen Antwort 
einen Beweis mit Hilfe des 
Pumping-Lemmas oder einer
geeigneten Reduktion. Es ist jeweils $\Sigma = \{0,1\}$.

\begin{enumerate}
\item $L_1 = \{0^m 1^{3m} \mid m \in \mathbb{N}\}$.
\item 
  $L_2 = \{\langle M\rangle \mid
  \text{Die Turing-Maschine $M$ akzeptiert die Eingabe $0110$.}\}$.
\end{enumerate}

$L_1$ ist \dots regul\"ar. $\Box$ Ja -- $\Box$ Nein
          \dots kontextfrei. $\Box$ Ja -- $\Box$ Nein\\
\phantom{$L_1$ ist}  \dots entscheidbar. $\Box$ Ja -- $\Box$ Nein
          \dots semientscheidbar. $\Box$ Ja -- $\Box$ Nein

$L_2$ ist \dots regul\"ar. $\Box$ Ja -- $\Box$ Nein
          \dots kontextfrei. $\Box$ Ja -- $\Box$ Nein\\
\phantom{$L_1$ ist}  \dots entscheidbar. $\Box$ Ja -- $\Box$ Nein
          \dots semientscheidbar. $\Box$ Ja -- $\Box$ Nein


\AUFGABE{Vermischtes}{3+3+4 Punkte}

\begin{enumerate}
  \item Richtig oder Falsch: 
    Sei $L \subseteq \{0,1\}^*$ eine kontextfreie 
    Sprache. Dann ist auch die Sprache
    $\{ \bar{w} \mid w \in L\}$ kontextfrei.
    Dabei ist $\bar{w}$ das Wort, welches man aus $w$
    erh\"alt, wenn man $0$ durch $1$ und $1$ durch $0$ ersetzt.
    Begr\"unden Sie Ihre Antwort.
  \item Sei $\Sigma = \{a,b\}$.
    Bestimmen Sie den jeweils spezifischsten Chomsky-Typ f\"ur die 
    folgenden drei Grammatiken. Geben Sie jeweils eine kurze Begr\"undung.
    \begin{enumerate}
       \item $S \rightarrow AA$; $A \rightarrow a$; $aAa \rightarrow b$.
       \item $S \rightarrow A \mid B$; $A \rightarrow a \mid BAB$; 
         $B \rightarrow bab$.
       \item $S \rightarrow bA \mid aB \mid a$; $A \rightarrow a \mid aB$; 
         $B \rightarrow b \mid a$.
    \end{enumerate}
  \item
    Sei $\Sigma = \{0,1\}$ und 
    $L = \{ 0^n1^{3n+5} \mid n \in \N\}$.
    Seien $w_1 = 101$, $w_2 = 001$ und $w_3 = 0111111$.
    Bestimmen Sie f\"ur jedes Wortpaar, ob die beiden
    W\"orter in der Nerode-Relation bez\"uglich
    $L$ \"aquivalent sind. Begr\"unden Sie Ihre Antworten.
\end{enumerate}

\AUFGABE{Reduktionen}{2+3+2+3 Punkte}

Bestimmen Sie f\"ur die folgenden Aussagen, ob sie
richtig oder falsch sind. Geben Sie jeweils einen Beweis
oder ein Gegenbeispiel an.
\begin{enumerate}
  \item F\"ur alle
     $L \subseteq \{0,1\}^*$ gilt $L \leq L$.
  \item F\"ur alle
     $L_1, L_2, L_3 \subseteq \{0,1\}^*$ folgt aus
     $L_1 \leq L_2$ und $L_2 \leq L_3$ auch $L_1 \leq L_3$.
  \item F\"ur alle
     $L_1, L_2 \subseteq \{0,1\}^*$ folgt aus
     $L_1 \leq L_2$ auch $L_2 \leq L_1$.
  \item Seien 
     $L_1, L_2 \subseteq \{0,1\}^*$ mit $L_1$ entscheidbar 
     und $L_2$ regul\"ar,  $L_2 \neq \{0,1\}^*$  und
     $L_2 \neq \emptyset$.
     Dann gilt $L_1 \leq L_2$.
\end{enumerate}

\end{description}
\end{document}
