Turing Maschine zeichnen |
| 08.05.2015, 22:55 | Tim1991 | Auf diesen Beitrag antworten » |
| Turing Maschine zeichnen ich muss im Fach Theoretische Informatik eine Turing Maschine zeichnen und wäre dankbar für ein paar Tipps. Eins vorweg: Wie eine Turingmaschine funktioniert und wie (nicht)deterministische Automaten funktionieren weiß ich. Zur Aufgabe: Gezeichnet werden soll Turingmaschine (DTM), die folgende Sprache akzeptiert: L = Meine Ideen: Erstmal führt ein Pfeil von Start- direkt in den Endzustand mit der Beschriftung #,#,R. Damit wäre das leere Wort Lambda abgedeckt. Liest man ein leeres Eingabeband nach rechts (R) ...#######..., und bricht ab, sobald man auf ein leeres Feld # trifft, wird akzeptiert. Weiter: Am Startzustand befindet sich noch eine Schleife mit der Beschriftung 0,0,R und 1,1,R. Wir lesen nämlich erstmal mit dem Lesekopf das gesamt Wort w, verändern es aber nicht. Wir prüufen nur, ob das Eingabewort aus der Sprache ist. Dann geht ein Pfeil aus dem Startzustand in den Zustand z1. Beschriftung des Pfeils: #,#,L. Damit gehen wir zurück auf den letzten Buchstaben des Wortes. Nun eine Schleife mit der Beschriftung: 0,0,L und 1,1,L an zustand z1. Damit gehen wir zurück zum Wortanfang. Dann noch ein Pfeil von z1 zu z2 mit der Beschriftung #,#,R. Dann sind wir an der ersten Stelle des Wortes. Da beginnt mein Problem: Wie zähle ich nun die Anzahl der Einsen und Nullen? Zähler einbauen hatten wir noch nicht. zahlen vorne und hinten löschen geht auch nicht einfach, weil ich nicht sicher stellen kann, dass für jede 0 eine 1 gelöscht wird. Und selbst wenn ich im Verhätnis 1:1 lösche, würde meine TM dann Wörter wie 1001000000010 nicht akzeptieren, weil das Wort zB deutlich mehr Nullen als Einsen hat (und nicht nur eine Null mehr). Könnt ihr mir Tipps geben, wie ich weiter machen kann? Vielen Dank schonmal! |
||
| 09.05.2015, 11:31 | Elvis | Auf diesen Beitrag antworten » |
Die Turingmaschine muss nicht zählen und vergleichen, sie muss nur etwas tun. Programmvorschlag: Setze z=0, lies ein Wort aus {0,1}* ein, und schreibe die ganze Zahl z=z-1 für 0 und z=z+1 für 1. Anzahl der 1 = Anzahl der 0 im Wort genau dann wenn z=0 am Ende des Wortes, also kann das Programm entscheiden, ob w aus L ist oder nicht. Jetzt muss Du nur noch eine Maschine bauen, die dieses Programm ausführt und Deiner Definition einer Turingmaschine entspricht. |
||
| 12.05.2015, 00:16 | FGIGast | Auf diesen Beitrag antworten » |
sitze grad am selbem problem, tipps sind gern gesehen |
||
| 12.05.2015, 01:33 | RavenOnJ | Auf diesen Beitrag antworten » |
Der Tipp von Elvis war doch gut. Ich hatte zwar noch eine andere Idee, diese Maschine ist allerdings nicht ganz so effektiv, wie die mit dem Zähler. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
