非正则语言的并集是否正则？两类特定语言并集相关技术咨询

Hey，我来逐个拆解你的这三个正则语言相关问题：

问题1：两个非正则语言的并集是否为正则语言？ #

答案是不一定，得看具体的语言：

• 有的时候，两个非正则语言的并集确实是正则的。举个例子：取非正则语言 ( L_1 = {a^n b^n \mid n \geq 0} )，它的补集 ( L_2 = \Sigma^* \setminus L_1 ) 肯定也是非正则的（毕竟正则语言的补集才是正则的，反过来非正则语言的补集不可能正则），而它们的并集就是所有由a和b组成的字符串 ( \Sigma^* )，这明显是正则的——用正则表达式 (a|b)* 就能描述。
• 但也有情况，两个非正则语言的并集还是非正则的。比如 ( L_1 = {a^n b^n \mid n \geq 0} )，( L_2 = {a^n b^n c^n \mid n \geq 0} )，两者都是非正则的，它们的并集包含了所有 ( a^n b^n ) 和 ( a^n b^n c^n ) 的字符串，这个集合没法用有限自动机识别，所以仍然是非正则的。

问题2：为何语言( L = L₁ ∪ L₂ = {aⁱbʲ \mid i,j ≥ 0} )是( L₁ = {aⁱbʲ \mid i ≥ j} )与( L₂ = {aⁱbʲ \mid i < j} )的并集？ #

核心就是逻辑上的穷尽性：对于任意两个非负整数 ( i ) 和 ( j )，要么 ( i \geq j )，要么 ( i < j )——这俩条件没有重叠，而且覆盖了所有可能的 ( i,j ) 组合。

换句话说，任何符合 ( a^i b^j )（( i,j \geq 0 )）的字符串，必然属于 ( L_1 ) 或者 ( L_2 )；反过来，( L_1 ) 和 ( L_2 ) 里的每一个字符串，都是 ( a^i b^j ) 形式的，所以把它们合起来，就正好是整个 ( L )。

问题3：( L₁ = {aⁱbʲ \mid i > j} )与( L₂ = {aⁱbʲ \mid i < j} )的并集是什么？ #

这个并集就是所有满足**( i \neq j )**的 ( a^i b^j ) 字符串，用集合表示就是：
[
{a^i b^j \mid i,j \geq 0 \text{ 且 } i \neq j}
]
换个更直观的说法，它等于所有 ( a^i b^j )（( i,j \geq 0 )）的集合，去掉那些 ( i = j ) 的特殊情况——也就是去掉 ( {a^n b^n \mid n \geq 0} ) 这个子集。

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