图灵机从3个字符的字母表中接受字符串

Question

我需要创建一个接受语言的图灵机a ^ 1 b ^ j c ^ k，其中i> = j> = k，但我甚至不确定如何开始。在这种情况下，图灵机是我难以理解的一个概念。

Answer 1

图灵机可以读写磁带并在磁带上来回移动。如果你有三种颜色的大理石线，你会怎么看他们是否像你的语言一样排列？您可以验证它们是否有序，然后分别计算每种颜色并确保关系成立。 “大于或等于”是二元关系，因此您可能需要单独检查两个对。使用三个额外的磁带非常容易想象：

1. 从左到右扫描以确保a先到先，然后是b，然后是c，然后返回到开头
2. 扫描正确计数a，为输入磁带上读取的每个磁带写一个a到额外的磁带＃1
3. 使用额外的磁带＃2继续扫描以计算b
4. 使用额外的磁带＃3继续扫描以计算c
5. 重置所有磁带头
6. 向右扫描以确保额外的磁带＃1中有更多的东西而不是额外的磁带＃2
7. 重置所有磁带头
8. 向右扫描以确保额外的磁带＃2中有更多的东西而不是额外的磁带＃3

如果我们不想使用额外的磁带，我们该怎么办？好吧，我们可以继续前进并确保符号的顺序是正确的......其余的更整齐。然后，我们可以“交叉”a和b对，直到所有b都耗尽（如果我们先耗尽所有b，那么halt_reject）;然后，解开b并交叉掉b和c对，直到你用完c（如果你先用完b，h​​alt_reject）。就像是...

 q    t    q'    t'    d

 q0   #    q1    #     right  //
 q1   a    q1    a     right  //
 q1   b    q2    b     right  //
 q1   #    q4    #     left   //
 q2   b    q2    b     right  // verify subset of
 q2   c    q3    c     right  // a*b*c*
 q2   #    q4    #     left   //
 q3   c    q3    c     right  //
 q3   #    q4    #     left   //

 q4   a    q4    a     left   //
 q4   b    q4    b     left   // reset input
 q4   c    q4    c     left   // tape to start
 q4   #    q5    #     right  //

 q5   a    q5    a     right  //
 q5   A    q5    A     right  // change susbtring a^j b^j
 q5   b    q6    B     left   // into substring A^j b^j
 q5   B    q5    B     right  // if run out of a, crash
 q5   c    q7    C     left   // if run out of b and no c, accept
 q5   #    h_a   #     left   // if run out of b and c, continue
 q6   a    q5    A     right  //
 q6   A    q6    A     left   //
 q6   B    q6    B     left   //

 q7   B    q8    D     right  //
 q7   C    q7    C     left   // change substring B^k c^k
 q7   D    q7    D     left   // to substring D^k c^k
 q8   D    q8    D     right  // if run out of B, crash
 q8   C    q8    C     right  // if run out of c, accept
 q8   c    q7    C     left   //
 q8   #    h_a   #     left   //

实施例1：aaabbc

   (q0, [#]aaabbc#) -> (q1, #[a]aabbc#) -> (q1, #a[a]abbc#) // 
-> (q1, #aa[a]bbc#) -> (q1, #aaa[b]bc#) -> (q2, #aaab[b]c#) // a*b*c*
-> (q2, #aaabb[c]#) -> (q3, #aaabbc[#]) -> (q4, #aaabb[c]#) //

-> (q4, #aaab[b]c#) -> (q4, #aaa[b]bc#) -> (q4, #aa[a]bbc#) //
-> (q4, #a[a]abbc#) -> (q4, #[a]aabbc#) -> (q4, [#]aaabbc#) // reset
-> (q5, #[a]aabbc#)                                         //

-> (q5, #a[a]abbc#) -> (q5, #aa[a]bbc#) -> (q5, #aaa[b]bc#) //
-> (q6, #aa[a]Bbc#) -> (q5, #aaA[B]bc#) -> (q5, #aaAB[b]c#) // a^j b^j
-> (q6, #aaA[B]Bc#) -> (q6, #aa[A]BBc#) -> (q6, #a[a]ABBc#) // A^j B^j
-> (q5, #aA[A]BBc#) -> (q5, #aAA[B]Bc#) -> (q5, #aAAB[B]c#) //
-> (q5, #aAABB[c]#) -> (q7, #aAAB[B]C#)                     //

-> (q8, #aAABD[C]#) -> (q8, #aAABDC[#]) -> (ha, #aAABD[C]#) // B^k c^k
                                                            // D^k C^k