19500 V Algorithmen und Programmieren I
Wintersemester 2003/2004

Rojas
Gloye


Übung 10

26. Januar 2004 (Abgabe Freitag, 6. Februar 2004)

Benutzen Sie das Haskell Programm turing_muster.hs zum Lösen der folgenden Aufgaben.

Aufgabe 1 (6 Punkte)

Implementieren Sie die Funktion show_states, die die Zustände der Maschine und den jeweiligen Inhalt des Bandes (1. Zeile), sowie die Bandposition (2. Zeile) unter dem Band anzeigt. Testen Sie das Programm im Framework.

Zum Beispiel:

Main> start (2,"A",'(',")A") klammer
  2  A()A
      T
  2  A()A
       T
  1  A(XA
      T
  2  AXXA
       T
  2  AXXA
        T
  3  AXXA
       T
  3  AXXA
      T
  3  AXXA
     T
  0  1XXA
     T

Aufgabe 2 (7 Punkte)

Implementieren Sie die Universelle Turing-Maschine als Programm (Zustandsübergangstabelle) für die Turing-Maschine (Zustandsübergangsdiagramm). Implementieren und testen Sie das Programm im Framework.

Aufgabe 3 (7 Punkte)

Schreiben Sie ein Programm (Symbole auf einem Band, keine Zustandsübergangstabelle aber sinnvoll formatiert) für die Universelle Turing-Maschine, das die Parität einer gegebenen Eingabe berechnet. Eine 0 soll als 00 und eine 1 als 11 kodiert werden. Für das Ende der Eingabe soll die Symbolkombination 10 verwendet werden. Das Ergebnis soll als 00 bei grader Parität und als 11 bei ungrader Parität über das Endesymbol geschrieben werden.


letzte Änderung am 26. Januar 2004 (Alexander Gloye)