如何为L={w∈{a,b}*|w≠xx^R,x∈{a,b}*}构造pushdown automata

注：$x^R$ 表示串 $x$ 的逆序，$L$ 等价于所有奇数长度的 ${a,b}$ 串 + 所有偶数长度且非回文的 ${a,b}$ 串。 #

形式化定义 #

构造非确定性下推自动机 $M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$，各参数定义如下：

• $Q = {q_{0e}, q_{0o}, q_1, q_{fail}, q_{acc}}$：状态集合
• $\Sigma = {a, b}$：输入字母表
• $\Gamma = {Z_0, a, b}$：栈字母表，$Z_0$ 为栈底符号
• $q_0 = q_{0e}$：初始状态（表示已读0个字符，为偶数长度）
• $Z_0$：初始栈符号
• $F = {q_{acc}}$：接受状态集合

状态转移规则 #

1. $q_{0e}$ 状态（已读偶数个字符，压栈阶段） #

对任意栈符号 $\gamma \in {Z_0, a, b}$：

• $\delta(q_{0e}, a, \gamma) = { (q_{0o}, a\gamma), (q_1, \gamma) }$：读到字符 a，要么压入栈、切换到奇数长度状态，要么非确定猜测已读够半段、跳转到匹配状态 $q_1$
• $\delta(q_{0e}, b, \gamma) = { (q_{0o}, b\gamma), (q_1, \gamma) }$：读到字符 b，逻辑同上
• $\delta(q_{0e}, \varepsilon, \gamma) = \emptyset$：偶数长度串，不触发奇数长度的接受逻辑

2. $q_{0o}$ 状态（已读奇数个字符，压栈阶段） #

对任意栈符号 $\gamma \in {Z_0, a, b}$：

• $\delta(q_{0o}, a, \gamma) = { (q_{0e}, a\gamma), (q_1, \gamma) }$：读到字符 a，要么压入栈、切换到偶数长度状态，要么非确定猜测已读够半段、跳转到匹配状态 $q_1$
• $\delta(q_{0o}, b, \gamma) = { (q_{0e}, b\gamma), (q_1, \gamma) }$：读到字符 b，逻辑同上
• $\delta(q_{0o}, \varepsilon, \gamma) = { (q_{acc}, \gamma) }$：输入读完、总长度为奇数，直接接受

3. $q_1$ 状态（匹配后半段阶段） #

对任意非栈底栈符号 $\gamma \in {a, b}$：

• $\delta(q_1, a, a) = { (q_1, \varepsilon) }$：输入字符与栈顶均为 a，匹配成功，弹出栈顶继续匹配
• $\delta(q_1, b, b) = { (q_1, \varepsilon) }$：输入字符与栈顶均为 b，匹配成功，弹出栈顶继续匹配
• $\delta(q_1, a, b) = { (q_{fail}, \varepsilon) }$：输入 a 与栈顶 b 不匹配，进入失败状态（此处失败指串不符合 $xx^R$ 的定义，属于待接受的情况）
• $\delta(q_1, b, a) = { (q_{fail}, \varepsilon) }$：输入 b 与栈顶 a 不匹配，进入失败状态
• $\delta(q_1, \varepsilon, \gamma) = \emptyset$：输入提前读完，匹配路径终止
• $\delta(q_1, a, Z_0) = \emptyset$：栈提前清空，匹配路径终止
• $\delta(q_1, b, Z_0) = \emptyset$：栈提前清空，匹配路径终止

4. $q_{fail}$ 状态（已出现不匹配，读完剩余输入） #

对任意输入字符 $\sigma \in {a,b}$、任意栈符号 $\gamma \in \Gamma$：

• $\delta(q_{fail}, \sigma, \gamma) = { (q_{fail}, \gamma) }$：跳过所有剩余输入，不修改栈

5. 空输入终态转移 #

• $\delta(q_1, \varepsilon, Z_0) = \emptyset$：匹配全部完成、串为 $xx^R$，拒绝
• $\delta(q_{fail}, \varepsilon, Z_0) = { (q_{acc}, Z_0) }$：匹配过程出现不匹配、总长度为偶数，符合 $L$ 定义，接受

正确性验证逻辑 #

充分性：若 $w \in L$，则 $M$ 接受 $w$ #

分两类场景验证：

1. $|w|$ 为奇数：所有奇数长度的串都不可能是 $xx^R$，属于 $L$。$M$ 读完所有输入后处于 $q_{0o}$ 状态，触发空输入转移到 $q_{acc}$，存在接受路径。
2. $|w|$ 为偶数且 $w \neq xx^R$：设 $|w|=2k$，由于 $w$ 不是偶回文，存在最小的 $1 \leq i \leq k$ 使得 $w[i] \neq w[2k -i +1]$。$M$ 可以非确定选择在读满 $k$ 个字符后跳转到 $q_1$ 状态，前 $k$ 个字符已全部压入栈；后续匹配过程中前 $i-1$ 次匹配均成功，第 $i$ 次匹配时输入字符与栈顶不匹配，进入 $q_{fail}$ 状态，读完剩余所有输入后触发空输入转移到 $q_{acc}$，存在接受路径。

必要性：若 $M$ 接受 $w$，则 $w \in L$ #

反证法验证：假设 $M$ 接受 $w$ 且 $w \notin L$，即 $w = xx^R$，设 $|x|=k$，则 $|w|=2k$。

• $w$ 是偶数长度，无法触发奇数长度的接受路径。
• 对任意猜测的匹配长度 $m$：
  • 若 $m \neq k$：匹配 $m$ 个字符后要么栈未空输入已结束，要么栈清空后仍有剩余输入，无有效转移到接受状态。
  • 若 $m = k$：后 $k$ 个字符与栈内前 $k$ 个字符完全匹配，最终处于 $q_1$ 状态，栈空且输入读完，无转移到接受状态。
    不存在任何接受路径，与假设矛盾，因此 $w \in L$。

内容的提问来源于stack exchange，提问作者Rajeev Ranjan Pan