Turingmaschine entwerfen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Sei = {a, b,X} und L = { wXw | w ∈ {a, b}∗ }. Die Sprache L enthält also Wörter mit genau einem X, das man wie ein Gleichheitszeichen für Wörter über {a, b} auffassen kann:
X ∈ L, aXa ∈ L, abXab ∈ L, abbabXabbab ∈ L, . . .
aba /∈ L, aX /∈ L, aXb /∈ L, abXabb /∈ L, . . .
Die Sprache L ist nicht vom Typ 2 (kontextfrei), sie kann also nicht von einem Kellerautomaten akzeptiert werden.
Geben Sie eine deterministische TuringmaschineM = (Z,, , δ, cC,_,E) mit T(M) = L an.
Wenn die Maschine hält, soll das Band genau das Eingabewort enthalten, der Lese-/Schreibkopf
auf dem ersten Zeichen dieses Eingabeworts stehen, und die Maschine im Zustand s0 sein
(wenn sie das Wort nicht akzeptiert) oder im Zustand s1 (wenn sie das Wort akzeptiert). |
Hallo,
Ich beiß mir an dieser Aufgabe absolut die Zähne aus, weil ich nicht auf das entscheidende Konzept komme:
Welche Möglichkeit hat die TM um sich dinge zu merken?
Wie soll ich am Ende vom Wort wissen was am Anfang des Wortes stand?!
Danke für Tipps oder auch die Lösung!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:20 Fr 25.09.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
