图灵机接受来自 3 个字符字母表的字符串

Question

我需要创建一个接受语言 a^1 b^j c^k 的图灵机，其中 i >= j >= k，但我什至不确定如何开始。由于某种原因，这种情况下的图灵机对我来说是一个很难掌握的概念。

Answer 1

图灵机可以读写磁带并在磁带上来回移动。如果你有一排三种颜色的弹珠，你怎么看它们的排列是否像你的语言中的字符串？您可以验证它们是否有序，然后分别计算每种颜色并确保关系成立。 "greater than or equal to" 是二元关系，因此您可能会分别检查这两对。这真的很容易想象使用三个额外的磁带：

从左往右扫描确保a在前，然后是b，然后是c，然后回到开头
向右扫描，计算 a，为您在输入磁带上读取的每个 a 将一个 a 写入额外磁带 #1
使用额外的磁带 #2 继续扫描以计数 b
使用额外的磁带 #3 继续扫描以计数 c
重置所有磁头
向右扫描以确保额外的磁带 #1 比额外的磁带 #2 包含更多内容
重置所有磁头
向右扫描以确保额外的磁带 #2 比额外的磁带 #3 包含更多内容

如果我们不想使用额外的磁带，我们该如何进行？好吧，我们可以继续，首先确保符号的顺序正确……让其余的更整洁。然后，我们可以 "cross off" 对 a 和 b，直到所有 b 都用完（如果我们先用完所有 a，则 halt_reject）；然后，取消 b 并划掉 b 和 c 对，直到你从 c 中运行（如果你先从 b 中运行，则 halt_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

图灵机接受来自 3 个字符字母表的字符串

Turing Machine to Accept String from a 3 character alphabet

discrete-mathematics

turing-machines