實作 Turing Machine 範例

Turing Machine 定義：

A Turing machine M is defined by (Q,S,G,d,qs,qa,qr)、with
‧ states Q ={qs,q0,q1,q2,q3,q4,qa,qr}
‧ input alphabet S = {>,0,1,u}
‧ start state qs 屬於 Q
‧ accept state qa 屬於 Q
‧ reject state qr 屬於 Q
‧ transition function d

   q 屬於 Q、     s 屬於 S   d(q、s)
     qs            0      (q0 、> 、R)
     qs            1      (q1 、> 、R)
     qs            >      (qs 、> 、R)
     qs            u      (qa 、u 、-)
     q0            0      (q0 、0 、R)
     q0            1      (q0 、1 、R)
     q0            u      (q2 、u 、L)
     q1            0      (q1 、0 、R)
     q1            1      (q1 、1 、R)
     q1            u      (q3 、u 、L)
     q2            0      (q4 、u 、L)
     q2            1      (qr 、1 、-)
     q2            >      (qa 、u 、R)
     q3            0      (qr 、1 、-)
     q3            1      (q4 、u 、L)
     q3            >      (qa 、> 、R)
     q4            0      (q4 、0 、L)
     q4            1      (q4 、1 、L)
     q4            >      (qs 、> 、R)

說明：輸入檔（input-1.txt）第一行表示有幾個 Turing Machine 迴圈要進行，輸出檔（out-1.txt） 1 表示接受，0 表示拒絕。

輸入：
3
>101u
>11000u
>1010u

輸出：
1
0
0

程式下載

原碼下載