如何证明正则语言相等？正则语言商运算等式真假判断

我整理了几种实用的方法，你可以根据具体场景灵活选用：

• 正则表达式等价变换：如果能把两种语言对应的正则表达式，通过等价规则（比如结合律、分配律、消除冗余的空串/闭包等）转换成完全一致的形式，就能证明它们对应的语言相等。
• 有限自动机等价验证：分别为两种语言构造DFA（确定有限自动机），然后对两个DFA做最小化处理。如果最小化后的DFA在状态数量、转移函数、起始状态、接受状态上完全匹配，那这两种正则语言就是相等的。另外也可以构造两个DFA的乘积自动机，检查是否不存在任何字符串仅被其中一个DFA接受——如果是这样，说明两个语言完全一致。
• 集合双向包含证明：这是最通用的方法，不管是不是正则语言都能用。证明第一个语言L₁是L₂的子集，同时L₂也是L₁的子集：任取一个属于L₁的字符串x，证明x也属于L₂；再任取属于L₂的字符串y，证明y也属于L₁。双向都成立的话，两个语言就相等。
• 闭包性质辅助验证：正则语言在补、交、差运算下都是封闭的。我们可以证明L₁ \ L₂和L₂ \ L₁都是空集——如果这两个差集对应的自动机没有接受状态，或者正则表达式为空，就说明两个语言没有差异，自然相等。

首先明确符号定义：L/a是语言L关于符号a的右商，具体定义是L/a = { w | wa ∈ L }，也就是所有满足“在末尾加上a后属于L”的字符串w的集合。而(L/a)a就是把L/a里的每个字符串后面都拼接上a，得到的新语言。

结论是：这个等式并不是恒成立的，我举两个例子帮你理解：

• 当L = {a}时，L/a = {ε}（因为空串ε加上a就是a，属于L），所以(L/a)a = {εa} = {a}，这时候等式成立。
• 但如果L = {aa, b}，情况就不一样了：L/a里的w必须满足wa∈L。wa=aa的话w=a；wa=b是不可能的（因为b的末尾是b不是a），所以L/a = {a}，那么(L/a)a = {aa}，而原L是{aa, b}，显然{aa} ≠ {aa, b}，这时候等式不成立。

本质原因是：(L/a)a其实是L中所有以a结尾的字符串的集合，所以它一定是L的子集（(L/a)a ⊆ L），但反过来，L中那些不以a结尾的字符串，永远不可能出现在(L/a)a里。只有当L中的每一个字符串都以a结尾时，(L/a)a才会等于L。

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