Dwustanowa maszyna Turinga do dopasowywania nawiasów

Na studiach poznawaliśmy ogólnie teorię obliczeń, a dokładniej maszyny Turinga. Jednym z wielkich wyników teoretycznych jest to, że kosztem potencjalnie dużego alfabetu (symboli) można zmniejszyć liczbę stanów do zaledwie 2.

Szukałem przykładów różnych maszyn Turinga, a częstym przedstawionym przykładem jest dopasowywanie / sprawdzanie nawiasów. Zasadniczo sprawdza, czy ciąg nawiasów, np. (()()()))()()()Jest zrównoważony (poprzedni przykład zwróciłby 0 za niezrównoważone).

Staram się, jak mogę, że mogę być tylko maszyną trójstanową. Chciałbym wiedzieć, czy ktokolwiek może sprowadzić to do teoretycznego minimum 2 i jakie było ich podejście / stany / symbole!

Dla wyjaśnienia, nawiasy są „umieszczone” pomiędzy pustą taśmą, więc w powyższym przykładzie - - - - - - - (()()()))()()() - - - - - - -byłoby wejściem na taśmę. Alfabet obejmowałyby (, ), 1, 0, -, a *halt*państwo nie liczy się jako państwo.

Dla porównania, trzy podejście stanowe, które mam, jest następujące: Opis stanów:

 State s1: Looks for Closing parenthesis

 State s2: Looks for Open parenthesis

 State s3: Checks the tape to ensure everything is matched

 Symbols: ),(,X

Przejścia wymienione jako:

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 -

Wybacz nieformalny sposób zapisywania tego wszystkiego. Wciąż uczę się teoretycznych konstrukcji.

Po prostu „kompendium kodu źródłowego” odpowiedzi Raphaela: to działająca wersja, która używa tej samej sztuczki (w stanie q1) i ma alfabet taśmy:
_ ( ) [ { / \ (gdzie$\_$ jest początkowym pustym symbolem)

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

Możesz to zobaczyć w pracy za pomocą internetowego symulatora maszyny Turinga ; kod źródłowy to:

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

Ostatnia uwaga: jeśli chcesz zobaczyć, jak tę technikę można wykorzystać do granic możliwości, przeczytaj (i spróbuj zrozumieć :-) budowę uniwersalnej maszyny Turinga z 2 stanami i 18 symbolami autorstwa Y. Rogozhina w „Small Universal Turing” maszyny ”

Głupia odpowiedź: twój wynik obiecuje, że istnieje uniwersalna maszyna Turinga z dwoma stanami. Skonstruuj dowolną bazę TM dla języka Dyck, oblicz jej indeks i zakoduj na stałe w uniwersalnej maszynie.

Ale to oczywiście nie jest bardzo satysfakcjonujące. Twoje podejście faktycznie działa, jeśli „oszukasz” różnicę między ruchem w lewo a ruchem w prawo, jednocześnie dopasowując pary nawiasów do rozszerzenia alfabetu. Potrzebujemy$\{\#,(,),x\}$ i oznaczone wersje $\hat{a}$ wszystkich symboli $a$.

• Stan początkowy $q_0$ działa w następujący sposób.

  Znajdując nieoznakowane symbole, przesuń w prawo, aż do pierwszego $)$jest znaleziony. W ten sposób zastąp wszystkie symbole$a$ z $\hat{a}$. Zastąp znalezione$)$ z $\hat{x}$.
  Jeżeli nie ma$)$, tzn. trafiliśmy w symbol przerwy $\#$, zastąp to $\hat{x}$ i przejdź do $q_1$.

  Znajdując oznaczone symbole, przesuń się w lewo, aż do pierwszego $\hat{(}$znaleziono, zastępując wszystkie przekazane (oznaczone) symbole ich nieoznakowanymi wariantami. Zastąp znalezione$\hat{(}$ z $x$.
  Jeśli znajdziemy$\hat{)}$ lub $\#$ po pierwsze, zapętl / odrzuć¹.

• W $q_1$, sprawdzamy, czy wszystko zostało dopasowane; wciąż mogą istnieć prefiksy formularza$\hat{(}^+$na taśmie. To znaczy, przesuń się w lewo, dopóki znajdziemy$\hat{x}$. Jeśli tak znajdziemy$\#$, zaakceptować; jeśli znajdziemy inny symbol, ale $\hat{x}$ po pierwsze, zapętl / odrzuć.

1. Jest to poprawne, ponieważ maszyna pasuje odwrotnie; w danych prawnych są tylko$x$ między parą nawiasów, które są obecnie dopasowane.