% 7. Uebungsblatt GTI SS 2001
\documentclass [11pt] {article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {german}
\usepackage[latin1]{inputenc}
\textwidth=16,1cm
\textheight=24cm
\hoffset = -19mm
\voffset = -25mm

\setcounter{page}{7}
\let\eps=\varepsilon
\begin{document}

\begin{centering}
{\large \bf Grundlagen der  theoretischen Informatik, SS 2001 ---
 7.~\"Ubungsblatt\par
% ENTWURF
}
\medskip
Abgabe bis Montag, 18. Juni 2001
\par \medskip
\end{centering}
\hrule
\medskip


\begin{enumerate}
\setcounter{enumi}{35}

\item (6 Punkte)
Beweisen Sie:
\begin{enumerate}
\item (6 Punkte)
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 (0 Punkte)
Eine Sprache $L$ ist genau dann entscheidbar, wenn sowohl die Sprache $L$ als
auch ihr Komplement $\bar L$ rekursiv aufzählbar ist.

\item (0 Punkte)
\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}
($D= \{\, w_i \mid
\hbox{$M_i$ akzeptiert $w_i$ nicht}\,\}$ ist die Diagonalsprache
und $\bar D$ ihr Komplement.)

\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 (6 Punkte)
Welche der folgenden Sprachen sind rekursiv,
 welche sind rekursiv aufzählbar?
\begin{enumerate}
\item (3 Punkte)
$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 (3 Punkte)
$L_4 = \{\,0^k \langle M \rangle w \mid
\hbox{$M$ akzeptiert $w$ nach mehr als $k$ Schritten.}\,\}$
\end{enumerate}

\item (4 Punkte)
Beiweisen 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 (0 Punkte)
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 
Jede reguläre Sprache ist rekursiv aufzählbar.
\item 
Jede Teilmenge einer regulären Sprache ist regulär.
\end{enumerate}

\end{enumerate}
\hrule
\medskip
Weil noch etwas Platz ist, seien hier noch einmal die Kriterien
für die Erlangung eines Übungsscheines in Erinnerung gerufen.%
\footnote{\tt
http://www.inf.fu-berlin.de/\char`\~rote/Lere/Grundlagen\%20der\%20theoretischen\%20Informatik/scheinkrit.html}
\begin{enumerate}
\item
60\,\% der Gesamtpunktezahl der Übungen.
(Die Übungszettel können in Dreiergruppen
oder in Zweiergruppen abgegeben werden.)
\item
Bei jedem Übungszettel bis auf einen müssen mindestens 30\,\% der Punkte erreicht werden. 
\item
50\,\% der Punkte bei der Zwischenklausur und 50\,\% der Punkte bei der Abschlussklausur 
(oder bei der entsprechenden Nachklausur).
\item
Aktive Teilnahme an den wöchentlichen Tutorien und
\emph{einmaliges Vorrechnen}
\end{enumerate}
Der Schein wird benotet. Die Note ergibt sich aus den Klausuren. 
\end{document}






