Mesin Turing Dua-Negara untuk Pencocokan Parenthesis

Di perguruan tinggi kami telah belajar tentang teori komputasi secara umum dan mesin Turing lebih khusus. Salah satu hasil teoretis yang hebat adalah bahwa dengan mengorbankan alfabet (simbol) yang berpotensi besar, Anda dapat mengurangi jumlah status menjadi hanya 2.

Saya mencari contoh Mesin Turing yang berbeda dan contoh umum yang disajikan adalah pencocokan / pemeriksa Parenthesis. Pada dasarnya ia memeriksa apakah sebuah tanda kurung, misalnya (()()()))()()()seimbang (contoh sebelumnya akan mengembalikan 0 untuk tidak seimbang).

Cobalah semaksimal mungkin saya hanya bisa menjadikan ini mesin tiga keadaan. Saya ingin tahu jika ada yang bisa mengurangi ini ke minimum 2 teoritis dan apa pendekatan / negara / simbol mereka!

Hanya untuk memperjelas, tanda kurung "terjepit" di antara pita kosong sehingga dalam contoh di atas - - - - - - - (()()()))()()() - - - - - - -akan menjadi input pada pita. Alfabet akan mencakup (, ), 1, 0, -, dan *halt*negara tidak dihitung sebagai sebuah negara.

Untuk referensi pendekatan tiga negara yang saya miliki adalah sebagai berikut: Deskripsi negara:

 State s1: Looks for Closing parenthesis

 State s2: Looks for Open parenthesis

 State s3: Checks the tape to ensure everything is matched

 Symbols: ),(,X

Transisi Terdaftar sebagai:

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 -

Maafkan cara informal menuliskan semua ini. Saya masih belajar teori konstruksi di balik ini.

Hanya ringkasan "kode sumber" dari jawaban Raphael: ini versi yang berfungsi yang menggunakan trik yang sama (pada status q1) dan memiliki alfabet tape:
_ ( ) [ { / \ (di mana adalah simbol awal kosong)$\_$

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

Anda dapat melihatnya bekerja menggunakan simulator online mesin Turing ; kode sumbernya adalah:

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

Catatan terakhir: jika Anda ingin melihat bagaimana teknik ini dapat didorong hingga batasnya, baca (dan coba pahami :-) konstruksi mesin Universal Turing dengan 2 status dan 18 simbol oleh Y. Rogozhin dalam "Small universal Turing mesin "

Jawaban bodoh: hasil Anda menjanjikan bahwa ada mesin Turing universal dengan dua status. Bangun TM apa pun untuk bahasa Dyck, hitung indeksnya dan cantumkan dalam mesin universal.

$\{\#,(,),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$