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

\setcounter{page}{9}
\begin{document}

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


\begin{enumerate}
\setcounter{enumi}{48}

\item
Ist es entscheidbar, ob eine Turingmaschine das leere Wort akzeptiert?
%
%\item
Ist es entscheidbar, ob eine Turingmaschine alle Wörter (also $\Sigma^*$) akzeptiert?

\item
%  \begin{enumerate}
%  \item 
Lösen Sie das Post'sche Korrespondenzproblem über einem
einelementigen Alphabet. % lösen?
%\item 
%Beweisen Sie, dass  das Post'sche Korrespondenzproblem über einem
%zweielementigen Alphabet unentscheidbar ist.
%\end{enumerate}

\item
Lösen Sie das Post'sche Korrespondenzproblem für folgende Eingaben:
\begin{enumerate}
\item $x_1,\ldots,x_5=
     abb,     a,       bab,     baba,     aba$;
$y_1,\ldots,y_5=
    bbab,    aa,      ab,      aa,       a$.
\item $x_1,\ldots,x_5=
    a,       baa,      abab ,    aabb ,    abb$;
$y_1,\ldots,y_5=
  ab,       ba  ,    bbaa ,    bbba  ,   bba$.
\item $x_1,\ldots,x_{10}=
d,de,deh,deh,deh,deha,deha,wa,wa,wah$;
$y_1,\ldots,y_{10}=
add,\allowbreak e,\allowbreak de,d,deha,eh,d,w,wah,wa$;
Welches sind die zwei kürzesten Lösungen?
\item (zum Tüfteln für alle, denen das
Post'sche Korrespondenzproblem zu leicht vorkommt)
 $x_1,\ldots,x_{4}= 001,01,01,10$;
$y_1,\ldots,y_{4}=0,011,101,001$.
\end{enumerate}
\item
Zeigen Sie, dass es unendlich viele Lösungen gibt, wenn das
Post'sche Korrespondenzproblem eine Lösung hat.

\item % (10 Punkte)  Reduzierbarkeit
\begin{enumerate}
\item (5 Punkte) Die algorithmische Reduzierbarkeit zwischen Problemen
  ist
 transitiv:
% eine transitive Relation:
Aus $A<B$ und $B<C$ folgt $A<C$.
%
%\item
Ist sie %die Reduzierbarkeit
 eine Ordnungsrelation?

\item (5 Punkte) Beweisen Sie: Wenn $A$ ein beliebiges entscheidbares
  Problem ist, so ist es auf das Halteproblem $H$ reduzierbar:
$A<H$.
\end{enumerate}

\item Wie kann man jede Turingmaschine \emph{ohne Zeitverlust} durch
  eine Turingmaschine simulieren, die sich nie über das erste
  Eingabezeichen nach links hinausbewegt?

\item (5 Punkte)  Wenn eine Turingmaschine $(Q,\Sigma,\Gamma,\delta,q_0,B,F)$ ein
  Wort $w$ in $t$ Schritten akzeptiert und sie dabei nur die ersten
$s$ Felder des Bandes besucht und sich nie über das erste
  Eingabezeichen nach links hinausbewegt,
dann ist
  $t \le |Q|\cdot s \cdot |\Gamma|^s$.

\item Betrachten Sie die "`Fleißige-Biber-Funktion"' für Programme in
  der Programmiersprache \textsc{Schleife} aus Aufgabe 1d,
  eingeschränkt auf Programme, in denen die Schleifenanweisungen
  höchstens bis zu einer vorgegebenen Tiefe $k$ %ineinander
  geschachtelt sind. % sein dürfen.
\begin{enumerate}
\item 
Beweisen Sie, dass diese Funktion %mit einer Turingmaschine
 berechenbar ist.
\item 
Beweisen Sie, dass diese Funktion für ein festes $k\ge 1$ nicht mit einem
\textsc{Schleife}-Programm der Schachtelungstiefe $k$ berechnet werden
kann. % (im Sinn von Aufgabe~37).

\item 
Was ist die Fleißige-Biber-Funktion für $k=0$ (Programme ohne
Schleife)?
Was ist das kürzeste Programm zur Berechnung dieser Funktion?
\end{enumerate}

\item Entwerfen Sie eine kontextsensitive Grammatik für die Sprache
$\{\, a^nb^nc^n \mid n\ge 1\,\}$.

\item Der erste Satz dieser Aufgabe ist ein Beispiel eines
  grammatikalisch korrekten Satzes.
Analysieren Sie diesen Satz gemäß der nachstehenden rudimentären Grammatik:
\begin{quote}
S $\to$ NG VG, 
NG $\to$ NG Att,
NG $\to$ Art NG$'$,
NG $\to$ NG$'$,
NG$'$ $\to$ Adj~NG$'$,
NG$'$ $\to$ N,
NG $\to$ Pro,
Att $\to$ NG,
Att $\to$ Präp NG,
VG~$\to$~V,
VG~$\to$ V Obj,
VG $\to$ V~Pr,
VG $\to$ VG~Erg,
Obj $\to$ NG,
Erg $\to$ Präp~NG,
Pr $\to$ Adj,
Pr $\to$ NG,
Adj $\to$ Adv Adj.
\end{quote}
(S = Satz, NG = Nominalgruppe,
 NG$'$ = Nominalgruppe ohne Artikel,
 VG = Verb"-gruppe, Att = Attribut, Art =
Artikel, Adj = Adjektiv, Adv = Adverb, N = Hauptwort (Nomen), Pro =
Pronomen, Obj = Objekt, Erg = %Ergänzung (
Modalobjekt,
Pr = Prädikat.)

Warum passt der zweite Satz dieser Aufgabe nicht zu dieser Grammatik?
\end{enumerate}
\end{document}
