\documentclass[12pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{graphicx}

\thispagestyle{empty}

\title{Theoretische Informatik - Übungsblatt 9}
\author{Jan Hendrik Dithmar - Matrikelnummer 2031259 \\
				Dirk Heine - Matrikelnummer 2030941 \\
		Di, 9-11 Uhr, Andreas Augustin \\
	}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\maketitle

\newpage

\section*{Aufgabe 1}
{\bfseries bearbeitet von Jan Hendrik Dithmar}
\subsubsection*{(a)}
$L$ r.e. $\Longrightarrow \overline{L}$ r.e. ist {\bfseries falsch}. \\
Gegenbeispiel: \\
$UNIV$ ist r.e., $\overline{UNIV}$ aber nicht.

\subsubsection*{(b)}
$L$ entscheidbar $\Longrightarrow \overline{L}$ entscheidbar ist {\bfseries wahr}. \\
Sei $M$ eine stets haltende TM, die genau die Wörter aus $L$ akzeptiert. Sei $q'$ ein neuer Zustand und $M'$ eine Erweiterung von $M$, in der nach dem Stoppen in einem nicht akzeptierenden Zustand in $q'$ gewechselt wird. Wenn wir definieren, dass $q'$ der einzige akzeptierende Zustand von $M'$ ist, hält $M'$ stets und akzeptiert $\overline{L}$.

\subsubsection*{(c)}
$L$ entscheidbar und $\overline{L}$ nicht r.e. $\Longrightarrow L$ regulär ist {\bfseries wahr}. \\
Die Voraussetzung kann nicht stimmen, da laut Vorlesung
$$L \text{ entscheidbar} \Longleftrightarrow L \text{ r.e. und } \overline{L} \text{ r.e.}$$
Somit kann $L$ entscheidbar und $\overline{L}$ nicht r.e. nicht gelten. \\
Nach den Gesetzen der Logik gilt folgendes: \\
$A \Longrightarrow B$ ist immer wahr, wenn $A$ falsch ist.

\subsubsection*{(d)}
$L \le L'$ und $L$ r.e. $\Longrightarrow L'$ r.e. ist {\bfseries falsch}. \\
$L \le L'\stackrel{Def.}{\Longleftrightarrow} \overline{L} \le \overline{L'}$. Wir wissen, dass $L$ r.e. ist. Also ist $\overline{L}$ nicht r.e. Da aber $\overline{L'}$ schwerer als $\overline{L}$ ist, ist auch dieses nicht r.e.

\subsubsection*{(e)}
$L \le L'$ und $L'$ r.e. $\Longrightarrow L$ r.e. ist {\bfseries wahr}. \\
Laut Vorlesung gilt:
\begin{enumerate}
	\item $L \le L'$ und $L'$ entscheidbar $\Longrightarrow L$ entscheidbar.
	\item $L$ entscheidbar $\Longleftrightarrow L$ r.e. und $\overline{L}$ r.e.
\end{enumerate}
Aus 1. und 2. folgt die Behauptung.

\subsubsection*{(f)}
$L \le L'$ und $L$ nicht r.e. $\Longrightarrow L'$ nicht r.e. ist {\bfseries wahr}. \\
Da $L$ leichter als $L'$ ist, kann sich bei der Reduktion von $L$ auf $L'$ keine entscheidbare Sprache ergeben.

\subsubsection*{(g)}
$L$ regulär $\Longrightarrow L$ entscheidbar ist {\bfseries wahr}. \\
$L$ regulär $\Longrightarrow L$ r.e. \\
Wegen der Abgeschlossenheit der regulären Sprachen unter Komplementbildung gilt auch: \\
$\overline{L}$ regulär $\Longrightarrow \overline{L}$ r.e. \\
Aus beiden Aussagen folgt: $L$ entscheidbar.

\subsubsection*{(h)}
$L$ kontextfrei $\Longrightarrow L$ r.e. ist {\bfseries wahr}. \\
$L$ r.e. bedeutet, $L$ ist Turing Sprache. Da NKA-Sprachen $\subset$ Turing Sprachen sind, gilt die Implikation.

\subsubsection*{(i)}
$L$ kontextfrei $\Longrightarrow L$ entscheidbar ist {\bfseries wahr}. \\
Baue eine TM $M$, die einen Kellerautomaten auf $L$ simuliert. $M$ akzeptiert die Eingabe, wenn der Kellerautomat akzeptieren würde. $M$ verwirft die Eingabe, wenn der Kellerautomat nicht akzeptiert.

\subsubsection*{(j)}
$L=\{\langle M \rangle \; | \; L(M) \text{ ist kontextfrei}\} \Longrightarrow L$ ist entscheidbar ist {\bfseries falsch}. \\
Nach dem Satz von Rice gilt die Implikation nicht.

\section*{Aufgabe 2}
{\bfseries bearbeitet von Dirk Heine} \\
Es gilt:
$$L = \{w \; | \; w = 0x \text{ für ein } x \in SAM \text{ oder } w = 1y \text{ für ein } y \in \overline{SAM}\}$$
Man betrachte 2 berechenbare Funktionen.
$$f: x \mapsto 0x, x \in SAM$$
$$g: y \mapsto 1y, y \in \overline{SAM}$$
Also ist $\overline{SAM}$ leichter als $L$ und $\overline{L}$.

\end{document}
