两种常规语言的交集可以是非常规语言吗？
您能举例说明何时发生这种情况吗？
不，保证两种常规语言的交集为常规语言。可以用很多方法证明这一点，但是一种简单的方法是使用闭包属性。假设您有普通语言L1和L2。这些语言有DFA M1和M2。将两台机器上的所有接受状态都更改为不接受，反之亦然；称结果机器为M1'和M2'。它们接受L1和L2的补语，它们必须是常规语言（因为有DFA接受它们）。因为这些补码是正则的，所以它们有正则表达式r1和r2。然后，正则表达式r = r1 + r2也描述了一种正则语言。因此，它具有DFAM。将M中的所有接受状态更改为非接受状态，反之亦然，以得到M'。 M'现在接受常规语言（L1'联合L2'）'。但是我们通过De Morgan知道，该表达式等效于L1与L2相交。
这是一个有建设性的证明，它向您展示了如何在给定L1和L2的DFA的情况下为L1相交的L2构建DFA。其他建设性的证明也是可能的。另一个流行的选择是使用笛卡尔积机器结构。这将为D1和L2中的每对状态生成一个DFA，且每个状态都有一个状态，并且这些转换将对应于从L1和L2中获取的转换对。