语言运算

集合运算只关心一个完整字是否属于语言；连接与星则利用字内部的先后次序。$KL$ 表达“先选择一段符合 $K$ 的字，再选择一段符合 $L$ 的字”，$L^{\ast }$ 表达把这种片段重复任意有限次。所谓任意包括零次，所以空字总在 $L^{\ast }$ 中；所谓有限则表示星不会产生无限字。

一个结果字可能有多种合法切分。若 $K=L=\{a,aa\}$，字 aaa 既可分成 a·aa，也可分成 aa·a。语言连接只记录结果是否存在某种切分，不记录切分见证，更不承诺唯一解析。需要保留语法树或捕获组时，语言集合本身的信息已经不够。

同态把每个输入符号替换成一个固定字，随后保持连接；它适合描述编码、擦除和 token 展开。逆同态从目标约束反推哪些源字会被映入其中。两者看似只是“替换字符串”，在闭包证明中却方向不同：像会合并多个源字，逆像则把一个目标语言拉回整个源空间。

设 $D=\{0,1,\dots ,9\}$，$S=\{\epsilon ,+,-\}$。那么 $S{D}^{+}$ 描述带可选符号且至少含一位数字的十进制整数字面量。这里 $S$ 含三个字，其中空字表示没有正负号；$D^{+}$ 排除了只写正负号的输入。若还要禁止前导零，需要再与一个更精确的语言组合。

令 $L=\{\mathtt{\text{ab}}\}$，则

它不包含 aabb，因为星重复的是整个片段 ab。同样，${\varnothing }^{\ast }=\{\epsilon \}$：正次数的幂都为空，零次幂仍贡献连接单位元。$\{\epsilon {\}}^{\ast }$ 也等于 $\{\epsilon \}$，但原因是每次选择的片段本身都为空。

连接一般不交换：$\{a\}\{b\}=\{ab\}$，而 $\{b\}\{a\}=\{ba\}$。它对并分配，例如 $K(L\cup M)=KL\cup KM$，却不会对交给出同样的等式；一个结果字在左右两边可能采用不同切分，因此通常只有 $K(L\cap M)\subseteq KL\cap KM$。

取 $K=\{\epsilon ,a\}$、$L=\{a\}$、$M=\{\epsilon \}$，便有 $L\cap M=\varnothing$，所以 $K(L\cap M)=\varnothing$。但 $KL=\{a,aa\}$、$KM=\{\epsilon ,a\}$，交集含 a：在第一边切成 $\epsilon \cdot a$，在第二边切成 $a\cdot \epsilon$。两个存在性见证各自成立，却没有一个共同右段落在 $L\cap M$ 中。

有限闭包不能越过到无限并。每个单点语言 $\{0^n{1}^n\}$ 都是正则语言，但

并不正则。一个语言类对二元并封闭，只能推出任意有限并封闭，不能跨过量词直接推广到可数并。

正则表达式理路正则表达式Regular expression从空语言、空字与单符号语言出发，经并、连接和 Kleene 星有限构造的语言表达式。正是以并、连接和 Kleene 星作为递归构造器。正则语言闭包性质理路正则语言闭包性质Closure properties of regular languages正则语言经有限布尔组合、连接、星、反转以及同态像和逆像后仍是正则语言。进一步说明，有限自动机所识别的语言经过哪些运算仍可由有限状态描述，并给出相应构造。

编译器用连接组织 token 序列，用并组合不同词法规则；协议规格把合法阶段语言连接起来；同态则能把详细事件归并为较粗类别，或把 token 展开成字符编码。每次使用补集或逆像时，都应同时检查字母表与映射的定义域，否则“所有其他输入”的范围会悄然改变。