可判定语言

阐述

如果存在一个对所有输入都会停机的 Turing 机（判定者）识别一个语言，则称它判定一个语言，语言是 Turing 可判定的。

我们可以将很多计算问题以测试某个字符串是否属于某个语言的形式表达，这个语言可判定等价于这个问题可判定。一些实例：

• 某个机器是否接受一个字符串
• 某个机器对应的语言是否为空
• 两个机器对应的语言是否相同

实例

与正则语言相关

$$A_{\text {DFA }}=\{\langle B, w\rangle \mid B \text { is a DFA that accepts input string } w\}$$ $$A_{\mathrm{NFA}}=\{\langle B, w\rangle \mid B \text { is an NFA that accepts input string } w\}$$ $$A_{\mathrm{REX}}=\{\langle R, w\rangle \mid R \text { is a regular expression that generates string } w\}$$ $$E_{\mathrm{DFA}}=\{\langle A\rangle \mid A \text { is a DFA and } L(A)=\emptyset\}$$ $$E Q_{\text {DFA }}=\{\langle A, B\rangle \mid A \text { and } B \text { are DFAs and } L(A)=L(B)\}$$

与上下文无关语言相关

$$A_{\mathrm{CFG}}=\{\langle G, w\rangle \mid G \text { is a CFG that generates string } w\}$$ $$E_{\mathrm{CFG}}=\{\langle G\rangle \mid G \text { is a } \mathrm{CFG} \text { and } L(G)=\emptyset\}$$

每个 CFL 都可判定。

其他

$$A_{\mathrm{LBA}}=\{\langle M, w\rangle \mid M \text { is an LBA that accepts string } w\}$$

反例

$$A_{\mathrm{TM}}=\{\langle M, w\rangle \mid M \text { is a TM and } M \text { accepts } w\}$$

性质

相关内容

参考文献