形式语言与自动机理论：两类语言的交集计算疑问

咱们先把两个语言的结构拆解开，看看它们末尾a的特征：

• 对于L₁ = {aⁿ bᵐ a | n ≥ 1, m ≥ 0}：
  这个语言里的每串字符，都是「至少1个a + 随便多少个b（包括0个） + 最后1个a」，所以末尾必然只有1个a——也就是末尾a的数量是奇数（1是奇数），不存在其他可能。

• 对于L₂ = {aⁿ b² a²ᵐ | n, m ≥ 0}：
  它的每串字符是「随便多少个a（包括0个） + 固定2个b + 偶数个a（0、2、4…个，因为2m，m≥0）」，所以末尾a的数量一定是偶数——哪怕m=0时末尾没有a，0也算偶数。

现在看交集的要求：一个字符串得同时属于L₁和L₂，那它必须同时满足「末尾a数量是奇数」和「末尾a数量是偶数」——这俩条件根本不可能同时成立，没有任何字符串能符合。所以L₁ ∩ L₂就是空集。

所以完全可以依据末尾a的奇偶性来计算两者的交集，直接得出交集为空的结论。

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