\documentclass{bschlangaul-aufgabe}

\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 5},
  Thematik = {Präfixrelation Entscheidbar},
  Referenz = 66112-2002-F.T2-A5,
  RelativerPfad = Examen/66112/2002/03/Thema-2/Aufgabe-5.tex,
  ZitatSchluessel = 66112:2002:03,
  BearbeitungsStand = nur Angabe,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Berechenbarkeit},
  EinzelpruefungsNr = 66112,
  Jahr = 2002,
  Monat = 03,
  ThemaNr = 2,
  AufgabeNr = 5,
}

Zeige,\index{Berechenbarkeit} \footcite{66112:2002:03} dass die
Präfixrelation (präfix(u,v): ↔ ∃w ∈ \{a, b\} * : uw = v) auf \{a, b\} *
entscheidbar ist.\footcite[Aufgabe 7a]{theo:ab:4}

% Die Entscheidbarkeit der Präfix-Relation ist gleichbedeutend damit, dass es eine termi-
% nierende Turingmaschine für die Präfix-Relation gibt, unter deren Schreib-/Lesekopf am
% Ende entweder 0 (d.h. w ∈
% / L) bzw. 1 (d.h. w ∈ L) steht.
% Die Eingabe steht zu Beginn folgendermaßen auf dem Band: \#u\#v\# und der Kopf sei
% ganz links.
% M = (Z, {a, b}, {a, b, \$, \#}, δ, Z 0 , \#, {Z F }), Z = {Z 0 , Z 1 , Z 2 , Z 3 , Z 4 , Z 5 , Z 6 , Z F }
% Start
% suche a
% suche b
% prüfe a
% prüfe b
% laufe zurück
% δ
% Z 0
% Z 1
% Z 2
% Z 3
% Z 4
% Z 5
% Z 6
% a (Z 1 , $, R) (Z 1 , a, R) (Z 2 , a, R)
% (Z 5 , $, L) (Z F , 0, N )
% (Z 6 , a, L)
% b (Z 2 , $, R)
% (Z 1 , b, R)
% (Z 2 , b, R) (Z F , 0, N ) (Z 5 , $, L)
% (Z 6 , b, L)
% \# (Z F , 1, N ) (Z 3 , \#, R) (Z 4 , \#, R) (Z F , 0, N ) (Z F , 0, N ) (Z 6 , \#, L)
% \$
% (Z 3 , $, R) (Z 4 , $, R) (Z 4 , $, R) (Z 5 , $, L) (Z 0 , \$, R)
\end{document}