TM 识别语言 ωωR：设计与实例解析

TM 识别语言 ωωR：设计与实例解析

本文介绍了使用图灵机 (TM) 识别由字符串 ω 和其逆串 ωR 构成的语言 ωωR 的方法。

TM 设计思想

1. 将输入字符串 ω 分成两部分，前半部分保存在一个辅助带中，后半部分反转保存在输入带中。
2. 从左到右遍历输入带和辅助带，逐个比较字符。如果不相等，则进入拒绝状态。
3. 如果遍历完输入带和辅助带都没有出现不相等的字符，则进入接受状态。

TM 定义

• Q： 状态集合 {q0, q1, q2, q3, q4}
• Σ： 输入字符集 {‘a’, ‘b’}
• Γ： 带字符集 {‘a’, ‘b’, ‘x’, ‘y’, ‘R’}
• δ： 转移函数
• q0： 起始状态
• q4： 接受状态
• q3： 拒绝状态
• B： 空字符
• F： 最终状态集合 {q4}

TM 转移函数

• δ(q0, ‘a’) = (q1, ‘x’, ‘R’)
• δ(q1, ‘a’) = (q1, ‘a’, ‘R’)
• δ(q1, ‘b’) = (q2, ‘y’, ‘R’)
• δ(q2, ‘a’) = (q2, ‘a’, ‘R’)
• δ(q2, ‘b’) = (q3, ‘b’, ‘R’)
• δ(q3, ‘a’) = (q3, ‘a’, ‘R’)
• δ(q3, ‘b’) = (q3, ‘b’, ‘R’)
• δ(q3, B) = (q4, B, ‘R’)

实例 abbbba 的识别过程

输入： _ ‘a’ ‘b’ ‘b’ ‘b’ ‘b’ ‘a’ _

状态： q0

带： _ ‘a’ ‘b’ ‘b’ ‘b’ ‘b’ ‘a’ _

状态： q1

带： _ ‘x’ ‘b’ ‘b’ ‘b’ ‘b’ ‘a’ _

状态： q1

带： _ ‘x’ ‘a’ ‘b’ ‘b’ ‘b’ ‘a’ _

状态： q1

带： _ ‘x’ ‘a’ ‘y’ ‘b’ ‘b’ ‘a’ _

状态： q1

带： _ ‘x’ ‘a’ ‘y’ ‘a’ ‘b’ ‘a’ _

状态： q2

带： _ ‘x’ ‘a’ ‘y’ ‘a’ ‘y’ ‘a’ _

状态： q3

带： _ ‘x’ ‘a’ ‘y’ ‘a’ ‘y’ ‘a’ B

状态： q4

识别成功，输入字符串 abbbba 是 ωωR 的形式。