% 6. Uebungsblatt GTI SS 2005
\documentclass [11pt] {article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {german}
\usepackage[latin1]{inputenc}
\textwidth=15cm
\textheight=24,5cm
%\textheight=26cm
\hoffset = -19mm
\voffset = -25mm
\let\eps=\varepsilon
\selectlanguage{ngerman}

\setcounter{page}{8}
\begin{document}

\begin{centering}
{\large \bf Grundlagen der  theoretischen Informatik, SS 2005 ---
 6.~\"Ubungsblatt\par
}
\medskip
Abgabe bis Montag, 30. Mai 2005, 10:15 Uhr
\par \medskip
\end{centering}
\hrule
\medskip


\begin{enumerate}
\setcounter{enumi}{41}

\item
Welche der beiden folgenden Aussagen sind wahr? Beweisen oder
widerlegen Sie sie.
\begin{enumerate}
\item
Wenn $L_1$ und $L_2$ entscheidbar sind, dann ist auch $L_1L_2$ entscheidbar.
\item % (0 Punkte)
Wenn $L_1$ und $L_2$ rekursiv aufzählbar
sind, dann ist auch $L_1L_2$ rekursiv aufzählbar.
\end{enumerate}

\item (10 Punkte)
$D= \{\, w_i \mid
\hbox{$M_i$ akzeptiert $w_i$ nicht}\,\}$ bezeichnet die Diagonalsprache
und $\bar D$ ihr Komplement.
\begin{enumerate}
\item
Zeigen Sie, dass die Sprache $\bar D$ rekursiv aufzählbar ist.
\item
Zeigen Sie, dass die Sprache $0D\cup 1\bar D$ nicht rekursiv aufzählbar ist.
\end{enumerate}

\item (2 Zusatzpunkte)
Eine andere Konstruktion einer unentscheidbaren Sprache.
$$U' := \{\, \langle M\rangle w \mid
\hbox{$M$ akzeptiert das Wort $\langle M\rangle w$ nicht}\,\}$$
(Der Beweis geht ähnlich wie bei der Diagonalsprache $D$.)

\item
Welche der folgenden Sprachen sind rekursiv,
 welche sind rekursiv aufzählbar?
\begin{enumerate}
\item
$L_1 = \{\,0^k \langle M \rangle w \mid
\hbox{$M$ akzeptiert $w$ nach höchstens $k$ Schritten.}\,\}$
\item 
$L_2 = \{\,0^k \langle M \rangle w \mid
\hbox{$M$ hat $w$ nach $k$ Schritten noch nicht akzeptiert.}\,\}$
\item $L_3 = \Sigma^* - (L_1\cup L_2)$
\item
$L_4 = \{\,0^k \langle M \rangle w \mid
\hbox{$M$ akzeptiert $w$ nach mehr als $k$ Schritten.}\,\}$
\end{enumerate}

\item
Beweisen Sie, dass die Sprache $L = \{\,0^i\mid i\ge0$, das
Teilwort $0^i123$ kommt in der Dezimaldarstellung von~$\pi$
unendlich oft vor$\,\}$ entscheidbar ist.
(Sie müssen dazu nichts über $\pi$ wissen, nur logisch
überlegen können. Wie kann $L$ aussehen?)

\item
Welche der folgenden Aussagen sind wahr, und welche sind falsch?
Welche Aussagen sind trivial, und welche sind absurd?
\begin{enumerate}
\item 
Jede Teilmenge einer rekursiven Sprache ist rekursiv.
\item 
Jede Teilmenge einer rekursiv aufzählbaren Sprache ist rekursiv aufzählbar.
\item 
Die Vereinigung zweier entscheidbarer Sprachen ist entscheidbar.
\item 
Die Vereinigung zweier rekursiv aufzählbarer Sprachen ist rekursiv aufzählbar.
\item 
Die Schnittmenge zweier entscheidbarer Sprachen ist entscheidbar.
\item 
Die Schnittmenge zweier rekursiv aufzählbarer Sprachen ist rekursiv aufzählbar.
\item 
Die Schnittmenge einer rekursiv aufzählbaren Sprache
und einer entscheidbaren Sprache ist rekursiv aufzählbar.
\item 
Jede reguläre Sprache ist rekursiv aufzählbar.
\item 
Jede Teilmenge einer regulären Sprache ist regulär.
\end{enumerate}

\item %(10 Punkte)
Zeigen Sie:
\begin{enumerate}
\item
Die rekursiven Sprachen sind unter Differenz
 abgeschlossen.
(Das heißt: Mit $L_1$ und $L_2$ ist auch $L_1-L_2$ immer rekursiv.)
\item Die rekursiv aufzählbaren Sprachen sind unter
Differenz nicht abgeschlossen.
\end{enumerate}


\end{enumerate}
\end{document}
