文章目录

• 一、图灵机设计示例 2
• 二、图灵机设计示例 3
• 三、图灵机设计示例 4

一、图灵机设计示例 2

---

给定语言 : $\mathrm{A}=\{\mathrm{w}|\mathrm{w}包含相同个数的0和1\}$ , 设计出该语言对应的图灵机 ;

$\mathrm{M}$ 图灵机算法设计如下 : 算法的描述是双引号 “” 中的内容 , 这是操作意义上的图灵机 , 只描述图灵机读头操作 , 没有必要将图灵机指令整体设计出来 ;

$\mathrm{M}=$ "在长度为 $\mathrm{n}$ 的字符串 $\mathrm{w}$ 上进行如下计算 :

① 返回带子最左端 , 从左向右扫描带子 , 找到 未标记的 $0$ , 标记后 , 转到 ② 继续运行 ; 如果没有找到未标记的 $0$ , 转到 ③ 运行 ;

② 返回带子最左端 , 从左向右扫描带子 , 找到 未标记的 $1$ , 标记后 , 转到 ① 继续运行 ; 如果没有找到未标记的 $1$ , 进入拒绝状态 ;

③ 返回带子最左端 , 从左向右扫描带子 , 找到未标记的 $1$ , 如果有则 进入拒绝状态 , 如果没有则 进入接受状态 ; "

二、图灵机设计示例 3

---

给定语言 : $\mathrm{A}=\{\mathrm{w}|\mathrm{w}包含0的个数是1的个数的两倍\}$ , 设计出该语言对应的图灵机 ;

$\mathrm{M}$ 图灵机算法设计如下 : 算法的描述是双引号 “” 中的内容 , 这是操作意义上的图灵机 , 只描述图灵机读头操作 , 没有必要将图灵机指令整体设计出来 ;

$\mathrm{M}=$ "在长度为 $\mathrm{n}$ 的字符串 $\mathrm{w}$ 上进行如下计算 :

① 返回带子最左端 , 从左向右扫描带子 , 如果没有发现 $0$ , 进入拒绝状态 ;

② 返回带子最左端 , 从左向右扫描带子 , 找到 两个未标记的 $0$ , 标记后 , 转到 ③ 继续运行 ; 如果没有找到未标记的 $0$ , 转到 ④ 运行 ; 如果发现一个未标记的 $0$ , 进入拒绝状态 ;

③ 返回带子最左端 , 从左向右扫描带子 , 找到 未标记的 $1$ , 标记后 , 转到 ② 继续运行 ; 如果没有找到未标记的 $1$ , 进入拒绝状态 ;

④ 返回带子最左端 , 从左向右扫描带子 , 找到未标记的 $1$ , 如果有则 进入拒绝状态 , 如果没有则 进入接受状态 ; "

三、图灵机设计示例 4

---

给定语言 : $\mathrm{A}=\{\mathrm{w}|\mathrm{w}包含0的个数不是1的个数的两倍\}$ , 设计出该语言对应的图灵机 ;

$\mathrm{M}$ 图灵机算法设计如下 : 算法的描述是双引号 “” 中的内容 , 这是操作意义上的图灵机 , 只描述图灵机读头操作 , 没有必要将图灵机指令整体设计出来 ;

$\mathrm{M}=$ "在长度为 $\mathrm{n}$ 的字符串 $\mathrm{w}$ 上进行如下计算 :

① 返回带子最左端 , 从左向右扫描带子 , 找到 两个未标记的 $0$ , 标记后 , 转到 ② 继续运行 ; 如果没有找到未标记的 $0$ , 转到 ③ 运行 ; 如果发现一个未标记的 $0$ , 进入接受状态 ;

② 返回带子最左端 , 从左向右扫描带子 , 找到 未标记的 $1$ , 标记后 , 转到 ① 继续运行 ; 如果没有找到未标记的 $1$ , 进入拒绝状态 ;

③ 返回带子最左端 , 从左向右扫描带子 , 找到未标记的 $1$ , 如果有则 进入接受状态 , 如果没有则 进入拒绝状态 ; "

总结

以上是生活随笔为你收集整理的【计算理论】计算理论总结 ( 图灵机设计示例 ) ★★的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。