文章目录
一、图灵机设计示例 2
二、图灵机设计示例 3
三、图灵机设计示例 4
一、图灵机设计示例 2
给定语言 : A = { w ∣ w 包 含 相 同 个 数 的 0 和 1 } \rm A = \{w | w 包含相同个数的 0 和 1 \}A={w∣w包含相同个数的0和1} , 设计出该语言对应的图灵机 ;
M \rm MM 图灵机算法设计如下 : 算法的描述是双引号 “” 中的内容 , 这是操作意义上的图灵机 , 只描述图灵机读头操作 , 没有必要将图灵机指令整体设计出来 ;
M = \rm M =M= "在长度为 n \rm nn 的字符串 w \rm ww 上进行如下计算 :
① 返回带子最左端 , 从左向右扫描带子 , 找到 未标记的 0 00 , 标记后 , 转到 ② 继续运行 ; 如果没有找到未标记的 0 00 , 转到 ③ 运行 ;
② 返回带子最左端 , 从左向右扫描带子 , 找到 未标记的 1 11 , 标记后 , 转到 ① 继续运行 ; 如果没有找到未标记的 1 11 , 进入拒绝状态 ;
③ 返回带子最左端 , 从左向右扫描带子 , 找到未标记的 1 11 , 如果有则 进入拒绝状态 , 如果没有则 进入接受状态 ; "
二、图灵机设计示例 3
给定语言 : A = { w ∣ w 包 含 0 的 个 数 是 1 的 个 数 的 两 倍 } \rm A = \{w | w 包含 0 的个数是 1 的个数的两倍 \}A={w∣w包含0的个数是1的个数的两倍} , 设计出该语言对应的图灵机 ;
M \rm MM 图灵机算法设计如下 : 算法的描述是双引号 “” 中的内容 , 这是操作意义上的图灵机 , 只描述图灵机读头操作 , 没有必要将图灵机指令整体设计出来 ;
M = \rm M =M= "在长度为 n \rm nn 的字符串 w \rm ww 上进行如下计算 :
① 返回带子最左端 , 从左向右扫描带子 , 如果没有发现 0 00 , 进入拒绝状态 ;
② 返回带子最左端 , 从左向右扫描带子 , 找到 两个未标记的 0 00 , 标记后 , 转到 ③ 继续运行 ; 如果没有找到未标记的 0 00 , 转到 ④ 运行 ; 如果发现一个未标记的 0 00 , 进入拒绝状态 ;
③ 返回带子最左端 , 从左向右扫描带子 , 找到 未标记的 1 11 , 标记后 , 转到 ② 继续运行 ; 如果没有找到未标记的 1 11 , 进入拒绝状态 ;
④ 返回带子最左端 , 从左向右扫描带子 , 找到未标记的 1 11 , 如果有则 进入拒绝状态 , 如果没有则 进入接受状态 ; "
三、图灵机设计示例 4
给定语言 : A = { w ∣ w 包 含 0 的 个 数 不 是 1 的 个 数 的 两 倍 } \rm A = \{w | w 包含 0 的个数不是 1 的个数的两倍 \}A={w∣w包含0的个数不是1的个数的两倍} , 设计出该语言对应的图灵机 ;
M \rm MM 图灵机算法设计如下 : 算法的描述是双引号 “” 中的内容 , 这是操作意义上的图灵机 , 只描述图灵机读头操作 , 没有必要将图灵机指令整体设计出来 ;
M = \rm M =M= "在长度为 n \rm nn 的字符串 w \rm ww 上进行如下计算 :
① 返回带子最左端 , 从左向右扫描带子 , 找到 两个未标记的 0 00 , 标记后 , 转到 ② 继续运行 ; 如果没有找到未标记的 0 00 , 转到 ③ 运行 ; 如果发现一个未标记的 0 00 , 进入接受状态 ;
② 返回带子最左端 , 从左向右扫描带子 , 找到 未标记的 1 11 , 标记后 , 转到 ① 继续运行 ; 如果没有找到未标记的 1 11 , 进入拒绝状态 ;
③ 返回带子最左端 , 从左向右扫描带子 , 找到未标记的 1 11 , 如果有则 进入接受状态 , 如果没有则 进入拒绝状态 ; "
