形式陈述

固定字母表 $\Sigma$$\mathrm{\Sigma }$，语言是 $\Sigma^*$${\mathrm{\Sigma }}^{\ast }$ 的子集。对语言 $L,M\subseteq\Sigma^*$$L,M\subseteq {\mathrm{\Sigma }}^{\ast }$，定义

$$ LM=\{xy:x\in L,\ y\in M\}, \qquad L^0=\{\varepsilon\}, \qquad L^{n+1}=L^nL, $$$$LM=\{xy:x\in L,y\in M\},L^0=\{\epsilon \},L^{n+1}=L^{n}L,$$$$ L^*=\bigcup_{n\ge0}L^n. $$$$L^{\ast }=\bigcup _{n\ge 0}{L}^n.$$

此外可作集合并、交、差与补；补集必须相对于明确的全集，通常是 $\Sigma^*$${\mathrm{\Sigma }}^{\ast }$。逆序定义为 $L^R=\{w^R:w\in L\}$$L^R=\{w^R:w\in L\}$。

直觉

集合运算按“是否属于语言”组合字符串，连接则按顺序拼接字符串，Kleene 星允许重复任意有限次并包含零次重复产生的空串。

例子与边界

若 $L=\{a,b\}$$L=\{a,b\}$，则 $L^2=\{aa,ab,ba,bb\}$$L^2=\{aa,ab,ba,bb\}$，且 $\varepsilon\in L^*$$\epsilon \in L^{\ast }$。$LM$$LM$ 通常不等于 $ML$$ML$。语言补集依赖字母表：同一字符串集合放在不同 $\Sigma^*$${\mathrm{\Sigma }}^{\ast }$ 中会有不同补集。

推论与应用

语言运算用于定义正则表达式和文法闭包性质。正则语言对并、交、补、连接与 Kleene 星封闭；不同语言类的闭包能力是判断表达能力的重要工具。

参考资料

• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，§§0.2–1.2。
• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006，Chapters 1–3。