\documentclass[a4paper,german]{article}

\usepackage[a4paper]{geometry}
\usepackage[utf8]{inputenc} % umlaute
\usepackage[ngerman]{babel} % auf deutsch umstellen -> auch deutsche trennung
\usepackage{array} % tabelle
\usepackage{graphicx} % für \includegraphics{}
\usepackage{calc} % für rechnungen
\usepackage{fancyhdr} % kopf und fußzeile
\usepackage[small]{caption} % für bildunterschriften % option: small
\usepackage{amsmath} % für begin{align}
\usepackage{color} % für farben
\usepackage{listings}
\usepackage{booktabs} % für \cmidrule
\usepackage{hhline} % für \hhline
\usepackage{setspace} % für zeilenabstand
\usepackage{amssymb} % für Mengen-minus ``\"
\usepackage{paralist} % compactitem
\usepackage{stmaryrd} % für \lightning
\usepackage{wasysym} % symbole.. \CheckedBox \Square \XBox
\usepackage{ifthen}
\usepackage{tikz}
\usetikzlibrary{arrows,automata,shapes}
\singlespacing    % einfacher zeilenabstand
% \onehalfspacing    % eineinhalbfacher zeilenabstand


% eigene commandos

\newcommand{\quickie}[2]{
\begin{minipage}{0.8\linewidth}
\vspace{0.1cm} % YOU THINK THIS IS UGLY? CODE IS UGLY BUT RESULT LOOKS GUUUUD
#1
\vspace{0.1cm}
\end{minipage}
\ifthenelse{\equal{\jobname}{\detokenize{bfs-braindump-2010-04-lsg}}}
    {
    \ifthenelse{\equal{#2}{true}}
        { & \XBox  & \Square \\ \hline }
        { & \Square  & \XBox \\ \hline }
    }
    { & \Square  & \Square \\ \hline}
}

\newcommand{\lsg}[1]{
    \ifthenelse{\equal{\jobname}{\detokenize{bfs-braindump-2010-04-lsg}}}
    { #1 }
    {  }
}

% seitenränder setzen
\topmargin 0in
\oddsidemargin 0.0cm % = 3cm abstand links
\textwidth 6.50in 
\textheight 9.15in

\pagestyle{fancy}

\lhead[ ]{BFS-Braindump vom 29.04.2011\lsg{ - Lösungsvorschlag, keine Garantie
auf Korrektheit! \smiley }}
\chead[ ]{}
\rhead[]{Seite \thepage}
\cfoot [] {\thepage}

\lstset{ %
language=C,
basicstyle=\footnotesize
}

\date{\today}
\renewcommand{\thesection}{\arabic{section}.}
\begin{document}
% settings:
\parindent 0pt % einrückung bei neuen absätzen deaktivieren
\parskip 6pt % abstand zwischen zwei absätzen
% eigentlicher content
\section{Aufgabe}
\begin{center}
\begin{tabular}{|l|ll|}
\hline
Frage & + & - \\ \hline
\quickie{
    Alle Sprachen in NP sind entscheidbar.
}{true}
\quickie{
    Sind zwei Sprachen $L_1$ und $L_2$ unentscheidbar, dann ist die symmetrische
    Differenz $L_1 \Delta L_2 := (L_1 \cup L_2) - (L_1 \cap L_2)$ auch
    unentscheidbar.
}{false}
\quickie{
    Die Sprache $L = \{\left<M\right>\mid M\text{ hält mindestens für die
    Eingaben $w_1$ und $w_2$}, w_1,w_2 \in \Sigma^*, w_1\neq w_2\}$ ist nicht
    rekursiv aufzählbar.
}{false}
\quickie{
    Wenn $L$ regulär ist, besitzt $L$ die kontextfreie Pumpeigenschaft.
}{true}
\quickie{
    Der Schnitt zweier kontextfreier Sprachen ist entscheidbar.
}{true}
\quickie{
    $L = \{\left<M\right>\mid \left<M\right> = w, M\text{ hat maximal
    }\log_2|w|\text{ Zustände}\}$ ist entscheidbar.
}{true}
\quickie{
    $L = \{\left<G,w\right>\mid G\text{ ist Grammatik in Chomsky NF und }w \in
    L(G)\}$, dann ist: $L \leq_p$ SAT}{true}
\quickie{
    Sei ein Graph $G = (V,E)$ gegeben und es sei $V'\subseteq V$ gegeben.
    Dann gibt es keine deterministiche 1-Band-Turingmaschine, die in polynomieller
    Zeit entscheidet, ob $V'$ eine unabhängige Menge in $G$ bilden.
}{false}
\quickie{
    Gegeben seien zwei Sprachen $A, B\subseteq\Sigma^*$. Wenn es eine total berechenbare Funktion
    $f: \Sigma^* \rightarrow \Sigma^*$ mit $x \in A \Leftrightarrow f(x) \in B$
    gibt,
    dann gilt: $A \leq B$
}{true}
\quickie{
    Sei $x$  die Binärdarstellung der natürlichen Zahl $(x)_2$, 
    $f(x) = (x)_2$, $f: \{0,1\}^+\rightarrow\mathbb{N}$. Ist $f$ bijektiv?
}{false}
\end{tabular}
\end{center}

\section{Aufgabe}
\textbf{a)} \\
Definieren Sie das initiale Halteproblem:\\
$H_\varepsilon := \{\lsg{
    \left<M\right> \mid M\text{ ist det. 1-Band-TM, die, gestartet mit leerem
    Band, hält} \}
} $

\textbf{b)} \\
$L_{2B} = \{ \left<M\right> \mid M\text{ berechnet bin}((x)_2^2) \}$, dabei ist
bin$(x)$ die Binärdarstellung von $x$ und $(x)_2$ wie oben definiert.
Zeigen Sie: $L$ ist nicht entscheidbar \\
Hinweis: Reduzieren Sie das unentscheidbare $H_\varepsilon$ auf $L_{2B}$. Zum
Beweis ,,$\Leftrightarrow$`` gehört ,,$\Rightarrow$`` und ,,$\Leftarrow$``.

%TODO: Beiweis?

\section{Aufgabe}
\textbf{a)} \\
Definieren Sie die kontextfreie Pumpeigenschaft:\\
$\lsg{\exists p \in \mathbb{N}: \forall z\in L, |z| \geq p: \exists u,v,w,x,y
\in \Sigma^*, uvwxy=z:
\left(|vwx| \leq p\right) \wedge
\left(|vx| \geq 1\right) \wedge
\left(\forall i \in \mathbb{N}_0: uv^iwx^iy \in L\right)}$

\textbf{b)} \\
Gegeben sei die Sprache:\\
$L_{3C} = \{ a^nb^mc^{n+m} \mid n,m \geq 0 \}$\\
Zeigen Sie durch direkte Anwendung der Definition, dass $L_{3C}$ die kontextfreie Pumpeigenschaft besitzt.

\textbf{c)} \\
Gegeben sei die Sprache:\\
$L_{3C} = \{ a^nb^mc^nd^m \mid n,m \geq 0 \}$\\
Zeigen Sie durch direkte Anwendung der Definition, dass $L_{3C}$ die kontextfreie Pumpeigenschaft nicht besitzt.

\section{Aufgabe}
\textbf{a)}
Gegeben sei der folgende Automat $A_1$:
\begin{center}
  \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node
    distance=5cm, semithick]
    \node[state,initial] (q0) {$q_0$};
    \node[state] (q2) [right of=q0] {$q_2$};
    \node[state,accepting] (q1) [below of=q0,xshift=2.5cm,yshift=3cm] {$q_1$};
    \node[state] (q3) [below of=q0,xshift=2cm] {$q_3$};
    \path (q0) edge [loop above] node {b} (q0)
          (q0) edge node {b} (q2)
          (q0) edge node {a} (q3)
          (q2) edge node {a} (q1)
          (q2) edge [bend left] node {b} (q3)
          (q1) edge node {$a|b$} (q3)
          (q3) edge [loop below] node {$b|a$} (q3);
  \end{tikzpicture}
\end{center}

Welche Sprache beschreibt der Automat $A_1$?\\
$L(A_1) =\lsg{L(b^*ba)}$

\textbf{b)}
Wandeln Sie den NFA $A_1$ in einen DFA um:


\textbf{c)}
Minimieren Sie den Automaten $A_2$ unter Beibehaltung der Eigenschaft, dass es
für jedes Zeichen einen Übergang gibt:
\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=5cm,
                    semithick]

  \node[state,initial] (A) {A};
  \node[state] (B) [below of=A] {B};
  \node[state] (C) [below of=A,xshift=2.5cm,yshift=2.5cm] {C};
  \node[state] (D) [right of=A] {D};
  \node[state,accepting] (E) [below of=D] {E};
  \path (A) edge node {1} (C)
        (A) edge node {0} (D)
        (C) edge node {0} (E)
        %(C) edge [loop above] node {1} (C)
        (E) edge node {0$\mid$1} (D)
        (B) edge node {0} (E)
        (C) edge node {1} (B)
        (B) edge [loop above] node {1} (B)
        (D) edge [loop above] node {0$\mid$1} (D)
  ;
\end{tikzpicture}
\end{center}

\lsg{
\begin{center}
\begin{minipage}{0.4\linewidth}
Lösung via NEQ:\\
\begin{tabular}{|r|c|c|c|c|}
\hhline{--}
 B &1\\ \hhline{---}
 C &1&ä\\ \hhline{----}
 D &2&1&1 \\ \hline
 E &0&0&0&0\\ \hline
   &A&B&C&D\\ \hline
\end{tabular}\\
(Hinweis: Nummern nicht verpflichtend)\\
$\Rightarrow B \equiv C$
\end{minipage}
\begin{minipage}{0.4\linewidth}
Das ergibt dann:\\
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2cm,
                    semithick]

  \node[state,initial] (A) {A};
  \node[state] (C) [below of=A] {[B]};
  \node[state] (D) [right of=A] {D};
  \node[state,accepting] (E) [below of=D] {E};
  \path (A) edge node {1} (C)
        (A) edge node {0} (D)
        (C) edge node {0} (E)
        %(C) edge [loop above] node {1} (C)
        (E) edge node {0$\mid$1} (D)
        %(B) edge node {0} (E)
        %(C) edge node {1} (B)
        (C) edge [loop left] node {1} (C)
        (D) edge [loop above] node {0$\mid$1} (D)
  ;
\end{tikzpicture}
\end{minipage}
\end{center}
}


\section{Aufgabe}

\textbf{a)}\\
Gegeben sei die Grammatik: \(G = (V, \Sigma, P, S)\).
Geben Sie die rekursive Definition der \mbox{$V(i,j) := \{A\mid A
\overset{*}{\rightarrow}a_i\ldots a_j\}$} ($i\leq j$), die der
CYK-Algorithmus verwendet, an:\\
$ \begin{array}{rl}
  V(i,i) &= \{\lsg{A \mid (A \rightarrow a_i) \in P\}}  \\ 
  V(i,j) &= \{\lsg{A \mid (A\rightarrow BC)\in P, B\in V(i,k), C\in V(k+1,j), k
  \in \{i,\ldots,j-1\}\}} 
\end{array} $

\textbf{b)}
Sei \(G = (V, \Sigma, P, S)\) und \(w = ababa\). Die Produktionen von $G$
lauten:
\begin{align*}
S &\rightarrow AB|BC    &   A &\rightarrow BA|a \\
B &\rightarrow CC|b     &   C &\rightarrow AB|a
\end{align*}
Vervollständigen Sie folgende Tabelle! Woran erkennen Sie, dass $w \in L(G)$?\\
\renewcommand\arraystretch{2.5}% (MyValue=1.0 is for standard spacing)
%\setlength{\extrarowheight}{0.8cm}
{
\begin{tabular}{|c|c|c|c|c|}
 \hline
 a     &       b &     a &     b &     a  \\ \hhline{-----}
\{A,C\}&    \{B\}&\{A,C\}&  \{B\}& \{A,C\}\\ \hhline{-----}
\{S,C\}&  \{S,A\}&\{S,C\}&\{S,A\}         \\ \hhline{----}
  \{B\}&  \{S,C\}&  \{B\}                 \\ \hhline{---}
$_{V(1,4)}$ & $_{V(2,5)}$ \\ \hhline{--}
$_{V(1,5)}$ \\ \hhline{-}
\end{tabular}
}
\lsg{
\begin{minipage}{0.5\linewidth}
$V(1,4) = \{B\} $ \\
$V(1,5) = \{S,A,C\} $ \\
$V(2,5) = \{B\} $ \\
$w \in L(G)$, da $S \in V(1,|w|) = V(1,5)$
\end{minipage}
}









\section{Aufgabe}
\textbf{a)}
Geben Sie die Definition des Überdeckungsproblems an:\\
$
VC = \{\lsg{\left<G,k\right> \mid G\text{ ist Graph }(V,E) \text{ und } \exists V' \subseteq V: |V| = k, \forall (u,v) \in E: u\in V'\vee v\in V'\}}
$

\textbf{b)}
Gegeben sei folgende Sprache:
\[ \textsc{MonotonSteigend} = \{ \text{bin}(a_1)\#\ldots\#\text{bin}(a_n) \mid
\forall i \in \{1\ldots n\}: a_i \in \mathbb{N}, \forall j \in \{1\ldots n-1\}: a_j \leq a_{j+1} \} \]
Zeigen Sie mittels Reduktion: \(\textsc{MonotonSteigend} \leq_p \textsc{Clique} \)
Hinweis: Zum Beweis ,,$\Leftrightarrow$`` gehört ,,$\Rightarrow$`` und
,,$\Leftarrow$``. Denken Sie daran, die Laufzeit Ihrer Reduktionsfunktion
anzugeben.

\textbf{c)}
Nehmen Sie an, es sei \(P = NP\). Ist dann {\sc MonotonSteigend} NP-Vollständig?













\end{document}
% vim: et tw=80
