2-Keller-Automat <-> Turingm. < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | (Definition eines Zwei-Keller-Automaten gemäß Wikipedia)
Zeigen Sie: Wird eine Sprache L von einer Turingmaschine erkannt, so auch von einem Zwei-Keller-Automaten. |
Hallo liebes Forum,
kann mir jemand evtl. eine Beweisidee nennen, mit der man o.g. Aussage zeigen kann? Es geht mir nicht um einen vollständigen Beweis, sondern lediglich um die Grundidee:
Wann wird was in dem einen Kellerspeicher verändert, und wann wird etwas im anderen Kellerspeicher geändert? Die Definition eines Zwei-Keller-Automaten mag leicht von der bei Wikipedia angegebenen abweichen, aber das Beweiskonzept sollte "passen" 
Die einzige Idee, die ich bislang hatte, war die, daß man die beiden Keller gemäß der Laufrichtung des Lese-/Schreibkopfes der Turingmaschine ändert. Also mit Sonderzeichen L und R (für "links" und "rechts"), mit denen man die Kellerspeicher jeweils beschreibt/verändert. Aber so richtig komme ich nicht auf den Knackpunkt :-/
Ein Tipp wäre super! Danke!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:20 So 31.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
