如何不借助NFA，用DFA证明正则语言的连接封闭性？

假设L₁、L₂是正则语言，分别由DFA M₁=(Q₁, Σ, δ₁, q₀₁, F₁)和M₂=(Q₂, Σ, δ₂, q₀₂, F₂)接受。我们直接构造接受L₁L₂={xy | x∈L₁, y∈L₂}的DFA M=(Q, Σ, δ, q₀, F)，具体步骤如下：

1. 状态集合定义 #

令Q为Q₁∪Q₂的所有子集构成的集合，即Q = ℘(Q₁ ∪ Q₂)。每个状态S∈Q表示当前输入字符串的前缀可能让我们处于M₁或M₂中的哪些状态——这是DFA的状态表示，无需借助NFA概念。

2. 初始状态 #

初始状态q₀ = {q₀₁}，对应输入为空串时，仅处于M₁的起始状态。

3. 终态集合 #

终态F包含所有满足S ∩ F₂ ≠ ∅的子集S∈Q。理由是：如果S包含M₂的终态，说明当前输入的字符串可以拆分为x∈L₁（让我们从M₁起始走到某终态，从而启动M₂的处理）和y∈L₂（让我们从M₂起始走到终态）。

4. 转移函数定义 #

对任意状态S∈Q、字符a∈Σ，δ(S, a)是以下两个集合的并集：

• 集合A：对S中所有属于M₁的状态q，计算δ₁(q, a)，将这些结果收集为集合A；
• 集合B：如果S中存在M₁的终态（即S ∩ F₁ ≠ ∅），则B为{δ₂(q₀₂, a)}；否则B为空集。

简单来说，转移时我们同时做两件事：

• 继续按照M₁的规则处理当前字符，跟踪可能的M₁状态；
• 如果之前已经匹配过L₁中的某个前缀，就从M₂的起始状态开始处理当前字符，跟踪对应的M₂状态。

5. 正确性验证 #

• 充分性：任取xy∈L₁L₂（x∈L₁，y∈L₂）。处理x时，M的状态会从{q₀₁}逐步转移到包含F₁中状态的子集Sₓ（因为M₁接受x）。处理y的第一个字符时，由于Sₓ∩F₁≠∅，转移会包含M₂起始状态处理该字符后的状态；后续处理y的每个字符，都会按M₂的转移更新状态，最终到达包含F₂中状态的子集，属于终态，故M接受xy。
• 必要性：任取被M接受的字符串w，处理完w后的状态S_w满足S_w ∩ F₂ ≠ ∅。这意味着处理过程中必然存在某个前缀x，使得处理x后的状态包含M₁的终态（否则无法启动M₂的转移），即x∈L₁；剩余部分y由M₂处理并到达终态，即y∈L₂，因此w=xy∈L₁L₂。

这样构造的M是严格的DFA（每个状态、每个输入字符对应唯一的转移状态），且无需借助NFA的任何概念，直接完成了连接封闭性的证明。

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