正则语言在连接与星运算下的闭包性质证明方法咨询

一、连接运算（L₁L₂）的闭包证明 #

正则语言的核心等价性是：语言是正则的当且仅当存在非确定有穷自动机（NFA）可识别它。我们通过构造NFA来证明L₁L₂的正则性：

1. 基础假设

   • 设M₁=(Q₁, Σ, δ₁, q₁, F₁)是识别L₁的NFA，M₂=(Q₂, Σ, δ₂, q₂, F₂)是识别L₂的NFA，且Q₁和Q₂不相交。

2. 构造新NFA M
   定义M=(Q₁∪Q₂, Σ, δ, q₁, F₂)，其中转移函数δ满足：

   • 保留M₁的所有转移：对任意q∈Q₁、a∈Σ∪{ε}，若δ₁(q,a)=p，则δ(q,a)=p；
   • 添加ε转移：对任意f∈F₁，δ(f, ε)=q₂（让M₁的所有终态能直接跳转到M₂的起始状态）；
   • 保留M₂的所有转移：对任意q∈Q₂、a∈Σ∪{ε}，若δ₂(q,a)=p，则δ(q,a)=p。

3. 正确性证明

   • 若w∈L₁L₂，则w可拆分为w=w₁w₂，其中w₁∈L₁、w₂∈L₂。M₁处理w₁后到达F₁中的某个状态，通过ε转移进入M₂的起始态q₂，再由M₂处理w₂到达F₂中的状态，因此M接受w。
   • 若M接受w，则w的处理路径必然是：先由M₁处理前缀w₁到达F₁，再通过ε转移进入M₂处理后缀w₂到达F₂。因此w=w₁w₂，且w₁∈L₁、w₂∈L₂，即w∈L₁L₂。

综上，L₁L₂可被NFA识别，是正则语言，正则语言对连接运算封闭。

二、星运算（L₁*）的闭包证明 #

同样基于NFA构造的思路，证明L₁*的正则性：

1. 基础假设

   • 设M₁=(Q₁, Σ, δ₁, q₁, F₁)是识别L₁的NFA。

2. 构造新NFA M
   定义M=(Q₁∪{q₀}, Σ, δ, q₀, {q₀}∪F₁)，其中q₀是新增的状态（同时作为起始态和终态），转移函数δ满足：

   • 添加ε转移：δ(q₀, ε)=q₁（从新起始态跳转到原M₁的起始态）；
   • 添加ε转移：对任意f∈F₁，δ(f, ε)=q₁（让M₁的终态能跳回起始态，实现重复匹配L₁中的字符串）；
   • 保留M₁的所有转移：对任意q∈Q₁、a∈Σ∪{ε}，δ(q,a)=δ₁(q,a)。

3. 正确性证明

   • 空串ε：q₀是M的终态，因此M接受ε，而ε∈L₁*。
   • 非空串w∈L₁*：w可拆分为w=w₁w₂...wₖ（k≥1），每个wᵢ∈L₁。M从q₀出发，经ε转移到q₁，处理w₁到达F₁中的状态，再经ε转移回q₁，重复此过程处理所有wᵢ，最终停在F₁或q₀（均为终态），因此M接受w。
   • 若M接受w：要么w是ε，要么w的处理路径是多次从q₁出发处理L₁中的字符串、再跳回q₁的过程，即w是L₁中字符串的连接，因此w∈L₁*。

综上，L₁*可被NFA识别，是正则语言，正则语言对星运算封闭。

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