Zwei-Zustands-Turingmaschine für die Klammeranpassung

Im College haben wir etwas über die Theorie der Berechnung im Allgemeinen und Turing-Maschinen im Besonderen gelernt. Eines der großartigen theoretischen Ergebnisse ist, dass Sie auf Kosten eines potenziell großen Alphabets (Symbole) die Anzahl der Zustände auf nur 2 reduzieren können.

Ich habe nach Beispielen für verschiedene Turingmaschinen gesucht und ein allgemeines Beispiel ist der Parenthesis Matcher / Checker. Im Wesentlichen wird geprüft, ob eine Folge von Klammern, z. B. (()()()))()()()ausgeglichen ist (das vorherige Beispiel würde 0 für unsymmetrisch zurückgeben).

Versuchen Sie, wie ich kann, ich kann nur erreichen, dass dies eine Drei-Zustands-Maschine ist. Ich würde gerne wissen, ob jemand dies auf das theoretische Minimum von 2 reduzieren kann und wie ihre Herangehensweise / Zustände / Symbole waren!

Zur Verdeutlichung sind die Klammern zwischen leerem Band "eingeklemmt", so dass im obigen Beispiel - - - - - - - (()()()))()()() - - - - - - -die Eingabe auf dem Band wäre. Das Alphabet würde (, ), 1, 0, -, und der *halt*Staat zählt nicht als Staat.

Als Referenz ist der Drei-Zustands-Ansatz, den ich habe, wie folgt: Beschreibung der Zustände:

 State s1: Looks for Closing parenthesis

 State s2: Looks for Open parenthesis

 State s3: Checks the tape to ensure everything is matched

 Symbols: ),(,X

Übergänge Aufgeführt als:

Action: State Symbol NewState WriteSymbol Motion

// Termination behavior
Action: s2 - *halt* 0  -
Action: s1 -  s3    -  r

//Transitions of TM
Action: s1 (  s1  (   l
Action: s1 )  s2  X  r
Action: s1 X  s1  X  l
Action: s2 ( s1 X  l
Action: s2 X  s2 X r
Action: s3 (  *halt* 0 -
Action: s3 X  s3     X r
Action: s3 -  *halt* 1 -

Vergib die informelle Art, das alles aufzuschreiben. Ich lerne immer noch die theoretischen Konstrukte dahinter.

Nur ein "Quellcode" -Kompendium von Raphaels Antwort: Dies ist eine Arbeitsversion, die denselben Trick verwendet (im Zustand q1) und das Bandalphabet hat:
_ ( ) [ { / \ (wobei das anfängliche leere Symbol ist)$\_$

q0:  _ -> accept  // accept on empty string and on balanced parenthesis
     ( -> {,R,q1  // mark the first open "(" with "{" and goto q1
     ) -> reject  // reject if found unbalanced ")"
     \ -> /,L,q0  // go left
     / -> \,R,q0  // go right

q1:  ( -> [,R,q1  // replace "(" with "[" and continue ...
     ) -> /,L,q1  // ... until first ")", replace it with "/" and goto left
     [ -> \,R,q1  // found matching "(" bracket, goto right and search for another ")"
     _ -> reject  // no ")" found for the first "{", reject
     { -> \,R,q0  // this must be the last match, goto q0 and check if it is true
     \ -> /,L,q1  // go left
     / -> \,R,q1  // go right

Sie können es bei der Arbeit mit einem Turing-Maschinen-Online-Simulator sehen . Der Quellcode lautet:

0 _ Y r halt
0 ( { r 1
0 ) N r halt
0 \ / l 0
0 / \ r 0
1 ( [ r 1
1 ) / l 1
1 [ \ r 1
1 _ N r halt
1 { \ r 0
1 \ / l 1
1 / \ r 1

Ein letzter Hinweis: Wenn Sie sehen möchten, wie diese Technik an ihre Grenzen gebracht werden kann, lesen Sie (und versuchen Sie zu verstehen :-) den Aufbau der Universal Turing-Maschine mit 2 Zuständen und 18 Symbolen von Y. Rogozhin in "Small Universal Turing" Maschinen "

Dumme Antwort: Ihr Ergebnis verspricht, dass es eine universelle Turing-Maschine mit zwei Zuständen gibt. Erstellen Sie ein beliebiges TM für die Dyck-Sprache, berechnen Sie den Index und codieren Sie es fest in die Universalmaschine.

$\{\#,(,),x\}$$\hat{a}$$a$

• $q_0$

  $)$$a$$\hat{a}$$)$$\hat{x}$
  $)$$\#$$\hat{x}$$q_1$

  $\hat{(}$$\hat{(}$$x$
  $\hat{)}$$\#$

• $q_1$$\hat{(}^+$$\hat{x}$$\#$$\hat{x}$

1. $x$