形式语言与自动机-各语言正反例

正规语言

正例

含特定子串
模运算计数：包含 3 的倍数个 a
有限集
开头结尾约束

反例

$L = {a^{n} b^{n} ∣ n \geq 0}$ ，没有内存

$L = {w w^{R} ∣ w \in {0, 1}^{*}}$
$L = {a^{n^{2}} ∣ n \geq 0}$ (长度为平方数)

上下文无关语言

正例

$L = {a^{n} b^{n} ∣ n \geq 0}$
- 读 $a$ 进栈，读 $b$ 出栈，栈空即接受。
$L = {w w^{R}}$
- 利用非确定性，猜到中间点，然后开始弹栈匹配。
$L = {a^{i} b^{j} c^{k} ∣ i = j 或 j = k}$
- CFL 对并集封闭。 $a^{n} b^{n} c^{*}$ 是 CFL， $a^{*} b^{n} c^{n}$ 也是 CFL，所以并集也是。

反例

$L = {a^{n} b^{n} c^{n} ∣ n \geq 0}$ (三方相等)
- 栈是线性的。匹配了 $a$ 和 $b$ 之后，栈就空了（或者 $a$ 已经被 $b$ 弹没了），没有东西留下来跟 $c$ 匹配
$L = {ww ∣ w \in {0, 1}^{*}}$
$L = {a^{n} b^{m} c^{n} d^{m}}$ (交叉依赖)

递归语言与递归可枚举语言

正例（递归语言）

$A_{D F A} = {⟨ D, w ⟩ ∣ DFA D accepts w}$
- 我们可以模拟 DFA，因为 DFA 一定在有限步内结束，所以是可判定的。
$A_{CFG} = {⟨ G, w ⟩ ∣ CFG G generates w}$
- 虽然 CFG 复杂，但可通过转换为乔姆斯基范式用 CYK 算法判定，一定会停机。

反例（是 RE，但不可判定 / 不是递归的）

$A_{TM} = {⟨ M, w ⟩ ∣ TM M accepts w}$
- 通用图灵机问题。我们可以模拟 $M$ 运行 $w$ ，如果 $M$ 接受，我们就接受。但如果 $M$ 死循环，模拟器也会死循环。所以它是 RE，但不可判定。
$H_{TM}$ (停机问题)：判断图灵机是否停机。

反例（连 RE 都不是 / 完全不可计算）

$\overline{A_{TM}}$
- **逻辑：如果一个语言 $L$ 和它的补集 $\overset{ˉ}{L}$ 都是 RE，那么 $L$ 一定是递归的（可判定）。因为 $A_{TM}$ 是 RE 但不可判定，所以它的补集一定不是 RE。
$L_{EQ} = {⟨ M_{1}, M_{2} ⟩ ∣ L (M_{1}) = L (M_{2})}$ (图灵机等价性)

总结表格

语言描述	类型	关键特征/判定理由
$a^{n} b^{m}$ (无约束)	正规	不需要计数，只需检查格式
$a^{n} b^{n}$ (n 次匹配)	CFL (非正规)	需要一个栈来计数
$a^{n} b^{n} c^{n}$ (三项匹配)	CSL (非 CFL)	栈不够用，需要线性有界内存
$w w^{R}$ (回文)	CFL	栈结构（先进后出）完美匹配
$ww$ (复制)	CSL (非 CFL)	需要队列结构（先进先出），栈做不到
$a^{n^{2}}$ (平方数)	CSL (非 CFL)	增长速度非线性（非泵引理模式）
代码语法检查	CFL (通常是 DCFL)	括号匹配、if-else 配对
判断 DFA 是否接受 $w$	递归 (可判定)	模拟一定会结束
判断 TM 是否接受 $w$	RE (不可判定)	可能会死循环
判断 TM 是否拒绝 $w$	非 RE	连死循环都检测不到