Ich erinnere mich an eine Grundschulklasse, dass es für eine Turing-Maschine mit einem endlichen Band immer entsprechende Automaten für den endlichen Zustand gibt, aber ich konnte dies nirgendwo im Internet bestätigen. Ist das tatsächlich der Fall oder erinnere ich mich falsch?
turing-machines
finite-automata
Jesse Berlin
quelle
quelle
Antworten:
Es kommt darauf an, was Sie unter "endlichem Band" verstehen. Wenn Sie die Länge des Bandes durch eine Funktion der Eingabe begrenzt haben, dann nein - Sie können nicht reguläre Sprachen erkennen. Betrachten Sie beispielsweise LBAs .
Um dies zu beweisen, überlegen Sie, welche Informationen Sie benötigen, um die Zukunft eines TM-Laufs zu bestimmen: Sie benötigen den Inhalt des Bandes, die Position des Kopfes und den Status. Wenn das Band eine konstante Anzahl von Zellen hat und das Alphabet fest ist, haben Sie eine konstante Anzahl von Konfigurationen, die Sie als Zustände eines endlichen Automaten codieren können.
quelle