如何求解 a^nb^nc^n 的图灵机示例 | n>=1？

Question

我正在努力解决这个挑战：

构建图灵机 𝐿 = { 𝑎^𝑛𝑏^𝑛𝑐^𝑛 | 𝑛≥1 }

我的回答：

^(q1,a)=(X,q2,R)
^(q2,a)=(a,q2,R)
^(q2,b)=(Y,q3,R)
^(q3,b)=(b,q3,R)
^(q3,c)=(Z,q4,L)
^(q4,b)=(b,q4,L)
^(q4,Y)=(Y,q4,L)
^(q4,a)=(a,q4,L)
^(q4,X)=(X,q1,R)
^(q1,a)=(X,q2,R)
^(q2,Y)=(Y,q2,R)
^(q2,b)=(Y,q3,R)
^(q3,Z)=(Z,q3,R)
^(q3,c)=(Z,q4,L)
^(q4,Z)=(Z,q4,L)
^(q4,Y)=(Y,q4,L)
^(q4,Y)=(Y,q4,L)
^(q4,X)=(X,q1,R)
^(q1,Y)=(Y,q2,R)
^(q2,Y)=(Y,q2,R)
^(q2,Z)=(Z,q2,R)
^(q2,Z)=(Z,q2,R)
^(q2,B)=(B,q5,N)

我在一些输入字符串上进行了测试，例如

aabbcc

。这个答案对吗？

Answer 1

看来是对的 这个想法是： 将第一个a转到X，然后向右找到第一个b，将其转到Y，向右找到第一个c，将其转到Z，回到第一个再次a。 这个过程一直持续到头下的第一个字母是Y而不是a。这意味着所有 a 都已与 b 和 c 匹配。 然后头部需要向右移动，经过 Y 和 Z，直到到达空白。