Übung Turingmaschine

Aus Informatik
Wechseln zu: Navigation, Suche



Aufgabe 1

Untersuche wie das Beispiel der Addiermaschine arbeiten. Schreibe dafür jeweils ein Programm für den Turing-Simulator.



Aufgabe 2

Teste die im Artikel Turingmaschine angegebene Turingmaschine mit dem Turing-Simulator und beschreibe, was die Maschine leistet. Lege (für das Wort 101101 auf dem Arbeitsband) ein Ablaufprotokoll an.



Aufgabe 3

Wozu dient die Turingmaschine mit diesem Zustandsgraphen?

Turingmaschine aufg 01.png



Aufgabe 4

Konstruiere eine Turingmaschine, die zu einem gegebenen Wort das Spiegelwort erzeugt und dieses durch ein Leerzeichen getrennt vom Original ausgibt.



Aufgabe 5

Die Sprache L= \{a^nb^nc^n~\vert~n \in \mathbb{N} \} ist uns hinlänglich bekannt. Erstelle eine Turingmaschine, die Worte dieser Sprache erkennt. Für welche praktischen Probleme ist diese Sprache interessant?



Aufgabe 6

Eine Turingmaschine soll Strichfolgen ungradzahliger Länge, also |, |||, |||||, ... akzeptieren (Paritätsprüfer). Erstelle und teste eine geeignete Turingmaschine.



Aufgabe 7

Gegeben ist eine natürliche Zahl n in unärer Darstellung, d. h. als Folge von genau n Strichen. Konstruiere eine Turingmaschine, die das Doppelte dieser Zahl erzeugt.



Aufgabe 8

Die Mephistofolge ist eine rekursiv definierte Folge aus Dualziffern. Mephisto ist bekanntlich "der Geist, der stets verneint". Demnach sind die ersten Folgenglieder: 0, 01, 0110, 01101001, 0110100110010110, ....

  1. Zuerst sollte man über ein Turingmaschine nachdenken, die lediglich eine beliebige Folge von 0 und 1 kopiert (ohne Zwischenzeichen).
  2. Entwerfe eine Turingmaschine mit dem Eingabealphabet X= {0,1} und dem Bandalphabet B= {0,1,#,X}, die an ein gegebenes Wort, das verneinte anhängt.
  3. Entwerfe eine Turingmaschine mit dem Eingabealphabet X= {0,1} und dem Bandalphabet B= {|,0,1,#,X}, die zum Eingabewort n in unärer Darstellung das n-te Folgeglied der Mephistofolge ermittelt. Sie soll z. B. die Anfangskonfiguration
    ...###|||###...
    in die Endkonfiguration
    ...###0110###...
    überführen.



Aufgabe 9

Gesucht ist eine Turingmaschine für den Divisionsrest modulo 4. Dabei soll die eingegebene unäre Zahl erhalten bleiben und der Divisionsrest durch ein Leerzeichen getrennt dahinter stehen. Z. B. soll die Ausgangskonfiguration
...###|||||||###...
in die Endkonfiguration
...###|||||||#|||###...
überführt werden.



Aufgabe 10

Zu Konstruieren ist eine Multipliziermaschine. Diese Turingmaschine erwartet die beiden Faktoren n bzw. m durch n bzw. m Striche codiert und durch genau ein Leerzeichen getrennt. Der Lese-/Schreibkopf steht in Standardposition auf dem ersten Strich. Das Produkt n*m steht durch ein Leerzeichen getrennt hinter den beiden nicht gelöschten Faktoren. Der Lese-/Schreibkopf steht nicht in Standardposition. Die Multipliziermaschine überführt z. B. die Anfangskonfiguration
... #III#II#...
in die Endkonfiguration
...*III*II*IIIIII*...



Aufgabe 11

Weitere Ideen, die im Unterricht entstanden ...

  1. Erkennen einer Folge von a's, b'c und c's, die gemischt stehen können, aber in jeweils gleicher Anzahl vorkommen müssen.
  2. Addition zweier I-Folgen bei Erhalt der Aufgabe
  3. Kodierer Strichliste => Binärzahl (und umgekehrt)
  4. Addition von Binärzahlen