子集与简单集合运算：寻找使两个包含式不成立的语言反例

嘿，这俩包含式不成立的边界例子其实很好构造，我给你举两个直观的实例，一步一步验证清楚：

1. 让 $A(B ∩ C) ⊇ AB ∩ AC$ 不成立的例子 #

我们的目标是找到一个字符串，它同时属于 $AB$ 和 $AC$，但不属于 $A(B ∩ C)$。具体构造如下：

设字母表 $\Sigma = {0,1}$，定义三个语言：

• $A = {\varepsilon, 0}$（$\varepsilon$ 代表空字符串）
• $B = {1}$
• $C = {01}$

现在计算两边的集合：

• $AB$：把A里的每个元素和B里的元素拼接，得到 ${\varepsilon \cdot 1, 0 \cdot 1} = {1, 01}$
• $AC$：同理，拼接后得到 ${\varepsilon \cdot 01, 0 \cdot 01} = {01, 001}$
• 两者的交集 $AB ∩ AC = {01}$

再看左边的 $A(B ∩ C)$：

• 先算 $B ∩ C$，${1}$ 和 ${01}$ 没有共同元素，所以 $B ∩ C = \emptyset$（空集）
• 空集和任何语言拼接还是空集，所以 $A(B ∩ C) = \emptyset$

很明显，$01$ 属于右边的 $AB ∩ AC$，但不属于左边的 $A(B ∩ C)$，所以这个包含式不成立。

2. 让 $A^* ∪ B^* ⊇ (A ∪ B)^*$ 不成立的例子 #

这个逻辑更简单：$(A ∪ B)^$ 包含所有由A、B中元素任意组合拼接的字符串，而 $A^$ 只能是A里元素的重复，$B^$ 同理。只要构造一个同时用到A和B元素的字符串，它就不在 $A^ ∪ B^*$ 里。

设字母表 $\Sigma = {a,b}$，定义：

• $A = {a}$
• $B = {b}$

计算两边：

• $(A ∪ B)^*$：所有由a和b组成的字符串（包括空串），比如 "ab"、"ba"、"aab" 这些都在里面
• $A^*$：只有全a的字符串，比如 ${\varepsilon, a, aa, aaa, ...}$
• $B^*$：只有全b的字符串，比如 ${\varepsilon, b, bb, bbb, ...}$
• $A^* ∪ B^*$：要么全a，要么全b，或者空串

拿字符串 "ab" 举例：它属于 $(A ∪ B)^$，但既不在 $A^$ 里（因为含b），也不在 $B^*$ 里（因为含a），所以这个包含式也不成立。

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