设计接受语言 L= {a^2 b^2n: n>=1} 的图灵机
Design a turing machine that accepts the language L= {a^2 b^2n: n>=1}
我想设计一个接受语言 L= {a^2b^2n: n>=1} 的图灵机
:. a 方 b 方(n)
如果您的语言是 a^2 b^2n = {aabb, aabbbb, aabbbbbb, ...}，则该语言是常规语言，它的 TM 首先读取两个 a，然后读取两个 b，然后是空白或另外两个 bs，直到找到空白。
q t q' t' d
-----------------------
q0 a q1 a right // read two a's from the
q1 a q2 a right // beginning of the tape
q2 b q3 b right // read at least two b's
q3 b q4 b right
q4 # hA # left // read more pairs of b's
q4 b q3 b right // or halt if input is done
如果您的语言是 a^2n b^2n = {aabb, aaaabbbb, aaaaaabbbbbb, ...}，则该语言是上下文无关的，它的 TM 会划掉匹配的 aa 和 bb，直到您 运行符号数。
q t q' t' d
-----------------------
q0 a q1 # right // erase two a's from
q1 a q2 # right // the front of the tape
q2 a q2 a right // scan to the end
q2 b q2 b right // of the tape
q2 # q3 # left
q3 b q4 # left // erase two b's from
q4 b q5 # left // the end of the tape
q5 a q5 a left // scan to the beginning
q5 b q5 b left // of the tape
q5 # q6 # right
q6 a q1 a right // try to start erasing a's
q6 # hA # - // or halt if all input is erased
我想设计一个接受语言 L= {a^2b^2n: n>=1} 的图灵机 :. a 方 b 方(n)
如果您的语言是 a^2 b^2n = {aabb, aabbbb, aabbbbbb, ...}，则该语言是常规语言，它的 TM 首先读取两个 a，然后读取两个 b，然后是空白或另外两个 bs，直到找到空白。
q t q' t' d
-----------------------
q0 a q1 a right // read two a's from the
q1 a q2 a right // beginning of the tape
q2 b q3 b right // read at least two b's
q3 b q4 b right
q4 # hA # left // read more pairs of b's
q4 b q3 b right // or halt if input is done
如果您的语言是 a^2n b^2n = {aabb, aaaabbbb, aaaaaabbbbbb, ...}，则该语言是上下文无关的，它的 TM 会划掉匹配的 aa 和 bb，直到您 运行符号数。
q t q' t' d
-----------------------
q0 a q1 # right // erase two a's from
q1 a q2 # right // the front of the tape
q2 a q2 a right // scan to the end
q2 b q2 b right // of the tape
q2 # q3 # left
q3 b q4 # left // erase two b's from
q4 b q5 # left // the end of the tape
q5 a q5 a left // scan to the beginning
q5 b q5 b left // of the tape
q5 # q6 # right
q6 a q1 a right // try to start erasing a's
q6 # hA # - // or halt if all input is erased