互补运算下如何显示正则语言是封闭的？

当我们对同一类的两种语言执行操作时，闭包属性是一种理解生成语言的类的技术。

这意味着，假设 L1 和 L2 属于正则语言，如果正则语言在操作∪ 下闭合，则 L1∪L2 将是正则语言。但是如果 RL 在 ∩ 下不封闭，那并不意味着 L1∩L2 不会是 RL。

对于要在操作下关闭的类，它必须适用于该类中的所有语言。所以，如果一个类在一个操作下没有被关闭，我们就不能说这个操作的结果语言的类——它可能属于也可能不属于操作数语言的类。

简而言之，闭包属性是适用的，只有当语言在操作下被关闭时才适用。

现在让我们证明常规语言在互补操作下是封闭的 -

问题

让两组的互补运算(COR)定义为 -

COR(A, B) = {x : x ∉ A or x ∉ B }，我们需要证明正则语言是封闭的

在 COR 操作下。

让 A 和 B 是常规语言。

COR(A, B) = {x : x ∉ A 或 x ∉ B }

=> { x : x ∈ A 的补码} ∪ {x : x ∈ B 的补码}。

如果 A 和 B 是正则的，

让 M1 = (Q1, ∑, δ1, q0, F1) 和

M2 = (Q2, ∑, δ2, p0, F2) 是接受 A 和 B 的 DFA。

然后 DFAs M1 的补码 = (Q1, ∑, δ1, q0, Q1 − F1) 和 M2 的补码 = (Q2, ∑, δ2, p0, Q2 − F2) 接受 A 的补码和 B 的补码。

因此，{ x : x ∉ A } 和 { x: x ∉ B } 是正则的。

那么根据上一题的结果，我们知道正则语言族在有限联合下是封闭的。

因此，我们得出结论，COR(A,B)是正规的