Turingmaschine konstruieren < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 08:55 Fr 05.04.2019 | | Autor: | Hela123 |
| Aufgabe | Für n [mm] \ge [/mm] 1 sei [mm]\Sigma = \left\{ a_1,a_2,...a_n \right\} [/mm] ein beliebiges Alphabet. Konstruieren Sie eine 1-Band Turingmaschine M mit maximal 5 Zuständen, die mit leerem Band gestartet das Alphabet auf das Band ausgibt. D.h. nach endlich vielen Schritten hält M, der Kopf zeigt auf das erste Bandquadrat und der Bandinhalt ist [mm] \$a_1\#a_2\#...\#a_n.
[/mm]
Beschreiben Sie Idee und Zustände von M. |
Hallo Forum,
ich verstehe nicht, wie ich diese Aufgabe eingehen soll. Wir sollen max 5 Zustände verwenden und dabei n mögliche Zeichen eingeben. Woher kann die Turingmaschine die Informationen über Alphabet nehmen? Ist es möglich so eine Art Iterator anzuwenden?
Ich stehe wirklich auf dem Schlauch und wäre für jeden Hinweis sehr dankbar!
Schönen Dank im Voraus
Hela123
|
|
| |
|
Wenn das Alphabet nicht aus Zahlen von 1 bis n besteht und nur 5 Zustände möglich sind, muss es eine Liste mit den Buchstaben geben. Diese kann jeweils als nummeriertes Unterprogramm aufgefasst werden, dass seine eigene Länge enthält und vom Hauptprogramm angesteuert wird. Grobplanung:
mache ein #
starte mit Nr i=1
(*)(schreibe die Nr. i aufs Band)
gehe zu Position i und lese, wo Buchstabe i beginnt.
Schreibe Buchstabe i hinter das letzte # und setze ein # dahinter.
Lies i, erhöhe es um 1 und gehe zu (*)
Du brauchst noch eine Abbruchbedingung und musst dir über die Möglichkeiten Gedanken machen, wo du die Nr. i hinschreibst. Sie kann ja theoretisch beliebig lang werden... Es fehlen auch sonst noch einige Details...
|
|
|
|
