
- 自动机理论教程
- 自动机理论 - 首页
- 自动机理论 - 入门
- 自动机理论 - 历史
- 自动机理论 - 应用
- 自动机理论术语
- 自动机中字符串的基础知识
- 自动机的集合论
- 语言和文法
- 计算理论中的文法
- 由文法生成的语言
- 乔姆斯基文法分类
- 有限自动机
- 确定性有限自动机 (DFA)
- 非确定性有限自动机 (NFA)
- 从 NFA 到 DFA 的转换
- DFA 的最小化
- 摩尔机与米利机
- DFA 的补集
- 正则表达式
- 自动机中的正则表达式
- 自动机中的 Arden 定理
- 将正则表达式转换为有限自动机
- 正则文法的泵引理
- 计算理论中的正则集
- 上下文无关文法
- 上下文无关文法 (CFG)
- 上下文无关文法中的二义性
- 上下文无关语言的闭包性质
- 简化上下文无关文法
- 乔姆斯基范式 (CNF)
- 格雷巴赫范式 (GNF)
- 上下文无关文法的泵引理
- 下推自动机
- 下推自动机 (PDA)
- 下推自动机的接受
- 由 CFG 构造 PDA
- 下推自动机和语法分析
- 图灵机
- 图灵机 (TM) 基础
- 图灵机接受的语言
- 多磁带图灵机
- 多轨迹图灵机
- 非确定性图灵机
- 半无限带图灵机
- 线性有界自动机 (LBA)
- 可计算性和不可判定性
- 图灵语言可判定性
- 不可判定语言
- 图灵机停机问题
- 计算理论中的 Rice 定理
- Post 对应问题 (PCP)
- 自动机理论资源
- 自动机理论 - 快速指南
- 自动机理论 - 资源
- 自动机理论 - 讨论
语言可判定性
如果存在一台图灵机,对于每一个输入字符串 w 都能接受并停机,则称该语言为可判定或递归语言。每个可判定语言都是图灵可接受的。

如果所有肯定例子的语言 L 是可判定的,则判定问题 P 是可判定的。
对于可判定语言,对于每个输入字符串,图灵机都会在接受状态或拒绝状态停机,如下图所示:

示例 1
找出以下问题是否可判定:
数字‘m’是否为素数?
解答
素数 = {2, 3, 5, 7, 11, 13, …………..}
从 ‘2’ 开始,将数字 ‘m’ 除以 ‘2’ 到 ‘√m’ 之间的全部数字。
如果任何这些数字产生余数为零,则进入“拒绝状态”,否则进入“接受状态”。因此,答案可以是“是”或“否”。
因此,这是一个可判定问题。
示例 2
给定一个正则语言 L 和字符串 w,我们如何检查 w ∈ L?
解答
取接受 L 的 DFA 并检查是否接受 w

一些其他的可判定问题:
- DFA 是否接受空语言?
- 对于正则集,L1 ∩ L2 = ∅ 是否成立?
注意:
如果语言 L 是可判定的,则其补集 L' 也是可判定的。
如果一个语言是可判定的,那么它就存在枚举器。
广告