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

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

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


\begin{enumerate}
\setcounter{enumi}{29}

\item (6 Punkte)
Binäre Addition.\\
Konstruieren Sie eine Turingmaschine, die die Summe zweier
Zahlen in Binärdarstellung berechnet.
Bei Eingabe von 
bin($x$){\tt\#}bin($y$){\tt\$}
soll die Maschine mit der Ausgabe
bin($x+y$){\tt\#}bin($y$){\tt\$}
und dem Kopf auf dem
ersten Eingabesymbol halten.
Dabei soll die Notation $\bin(x)\in\{0,1\}^*$ eine
Darstellung von $x\in \mathbb{N}$ in Binärdarstellung darstellen.
Der Automat soll am Ende in einen Zustand $q_F$ übergehen und
anhalten.
Ein eventueller Bandinhalt rechts vom \texttt{\$}-Zeichen soll
unverändert stehengelassen werden.

\emph{Beschreiben Sie Ihren Algorithmus zunächst in Worten.}

Geben Sie die ersten 15 und die letzten 10 Konfigurationen
Ihrer Turingmaschine bei Eingabe von
\texttt{101\#11\$} an.

\item (0 Punkte) Multiplikation.\\
Konstruieren Sie eine Turingmaschine, die zwei
"`unäre"' Zahlen multipliziert.
Bei Eingabe von $0^m1^n$ soll die Ausgabe $0^{mn}$ berechnet werden.

\item (0 Punkte)
\begin{enumerate}
\item 
Entwerfen Sie eine Turingmaschine, die die Sprache
$\{\, 0^n1^n0^n\mid n\ge 0\,\}$ akzeptiert.
\item
Entwerfen Sie eine Turingmaschine für dieselbe Sprache,
die mit dem Bandalphabet $\Gamma=\{0,1,B\}$ auskommt.

(Hinweis: Sie können ein größeres Bandalphabet "`simulieren"',
indem Sie es "`binär kodieren"'. Dabei wird
jeweils eine feste Anzahl von Feldern des Bandes zu einer
logischen Einheit zusammengefasst.)
\end{enumerate}

\item (5 Punkte) Definieren Sie formal die
Nachfolgerrelation $xqy \vdash x'q'y'$ für Konfigurationen
einer Turingmaschine. ($q,q'\in Q$,
$x\in \{\eps\} \cup (\Gamma-\{B\})\Gamma^*$,
$y\in \{\eps\} \cup \Gamma^*(\Gamma-\{B\})$.)

\item (0 Punkte) Speicherzugriff (Tabellenzugriff) über Adressen.
  \begin{enumerate}
  \item Lesen aus einer Tabelle.\\ Bei Eingabe von
   $$x=
\texttt\#
x_1\texttt|y_1\texttt\#
x_2\texttt|y_2\texttt\#
\ldots
\texttt\#
x_n\texttt|y_n
\texttt\$x_0
   $$
   mit $n\ge0$, $x_k,y_k\in\{0,1\}^*$
soll die Ausgabe $x\texttt|y$
berechnet werden.
Dabei ist $y=y_i$ für den größten Index $i\le n$ mit $x_i=x_0$, und
$y=0$, falls kein solches $i$ existiert.
  \item Löschen aus einer Tabelle.\\
Bei den gleichen Angaben wie oben soll die Ausgabe
   $$x=
\texttt\#
x_1\texttt|y_1\texttt\#
\ldots
\texttt\#
x_{i-1}\texttt|y_{i-1}\texttt\#
x_{i+1}\texttt|y_{i+1}\texttt\#
\ldots
\texttt\#
x_n\texttt|y_n
\texttt\$x_0
   $$
berechnet werden.
Wenn kein passender Index $i$ existiert, soll die Eingabe unverändert
gelassen werden.
  \end{enumerate}

\item (4 Punkte) Beweisen oder widerlegen Sie:
  \begin{enumerate}
  \item (4 Punkte) Das Komplement einer entscheidbaren Sprache ist
     entscheidbar.
  \item (0 Punkte) Die Vereinigung zweier entscheidbarer Sprache ist
     entscheidbar.
  \item (0 Punkte) Das Komplement einer unentscheidbaren Sprache ist
     unentscheidbar.
  \item (0 Punkte) Die Vereinigung zweier unentscheidbarer Sprache ist
     unentscheidbar.
  \end{enumerate}
\end{enumerate}

\end{document}
