如何基于原DFA构建NFA证明变换语言plus(L)的正则性？

嘿，这个问题其实是正则语言封闭性的典型应用场景，我来一步步给你拆解怎么用NFA构建来证明plus(L)的正则性～

我们已知L是正则语言，有对应的DFA M。要证明plus(L)正则，核心思路是：构造一个NFA，同时完成两件事——验证输入字符串确实是某个二进制数加1的结果，并且这个原二进制数属于L。

二进制加1的本质很好理解：从最低位开始找第一个0，把它变成1，后面的所有1全变成0；如果原数全是1，就直接在前面加个1，后面全变0（比如111→1000）。但自动机是从左到右读高位的，所以我们要把这个逻辑转化为“从高位到低位”的匹配规则：

• 加1后的数y和原数x，前面的若干高位是完全相同的；
• 直到遇到某一位：y是1，x是0（这就是那个被翻转的0）；
• 之后的所有位，y是0则x是1，y是1则x是0；
• 特殊情况：y是1后面跟全0，对应x是全1。

所以我们的NFA需要同时跟踪两个状态：原DFA M的当前状态（用来验证x属于L），以及是否已经触发了进位翻转的关键位（用来验证y=x+1）。

假设原DFA M = (Q, {0,1}, δ, q₀, F)，其中Q是状态集合，δ是转移函数，q₀是初始状态，F是接受状态。我们要构建的NFA N = (Q', {0,1}, δ', q'₀, F')：

1. 定义NFA的状态集合Q' #

Q' = Q × {0, 1} ∪ {q_start}

• (q, 0)：表示还没触发进位翻转，当前读到的y的前缀和x的前缀完全一致，同时原DFA处于状态q；
• (q, 1)：表示已经触发了进位翻转，后面的y的每一位都要和x的位相反，同时原DFA处于状态q；
• q_start：额外的初始状态，用来衔接原DFA的初始状态，处理所有特殊情况。

2. 初始状态与ε转移 #

NFA的初始状态是q_start，我们添加一条ε-转移：δ'(q_start, ε) = {(q₀, 0)}。意思是：从初始状态出发，直接进入“未触发翻转”的状态，同时开始用原DFA的初始状态跟踪原数x。

3. 转移函数的具体规则 #

分两种核心状态来定义转移：

当处于(q, 0)（未触发翻转） #

• 输入0：说明x的这一位也是0（因为还没翻转，y和x同步），所以转移到(δ(q, 0), 0)——原DFA读0后进入新状态，同时保持未翻转状态；
• 输入1：这里有两种可能：
  1. 这一位x也是1（还没到翻转位），转移到(δ(q, 1), 0)；
  2. 这一位x是0（就是我们要找的翻转位），转移到(δ(q, 0), 1)——原DFA读0，同时切换到已翻转状态。

当处于(q, 1)（已触发翻转） #

• 输入0：对应x的这一位是1（因为翻转后0变1），转移到(δ(q, 1), 1)；
• 输入1：对应x的这一位是0（翻转后1变0），转移到(δ(q, 0), 1)。

4. 接受状态的定义 #

NFA的接受状态F'包含所有满足以下条件的状态：

• (q, 1)，其中q ∈ F。
  解释：这个状态表示我们已经完成了进位翻转的所有操作，并且原DFA的状态q是接受状态——说明原数x属于L，对应的y=x+1自然属于plus(L)。

假设原DFA接受0111，现在看NFA如何接受1000：

1. 从q_start通过ε转移到(q₀, 0)；
2. 读第一个字符1：触发翻转，转移到(δ(q₀, 0), 1)（对应x的第一位是0）；
3. 读第二个字符0：对应x的第二位是1，转移到(δ(δ(q₀,0), 1), 1)；
4. 读第三个字符0：对应x的第三位是1，转移到(δ(δ(δ(q₀,0),1),1), 1)；
5. 读第四个字符0：对应x的第四位是1，转移到(δ(δ(δ(δ(q₀,0),1),1),1), 1)；
6. 最终这个状态的q是原DFA读完0111后的状态，而q ∈ F，所以这个状态属于F'，1000被接受，完全符合预期。

• 所有被NFA接受的y，都能找到对应的x∈L，使得y=x+1：每一条接受路径都严格对应二进制加1的逻辑，同时原DFA的状态跟踪确保x属于L；
• 所有plus(L)中的y，都会被这个NFA接受：不管是普通的翻转情况，还是全1变1后面跟全0的特殊情况，都能被NFA的转移规则覆盖到。

内容的提问来源于stack exchange，提问作者Dawn17