互补运算下如何显示正则语言是封闭的?
当我们对同一类的两种语言执行操作时,闭包属性是一种理解生成语言的类的技术。
这意味着,假设L1和L2属于正则语言,如果正则语言在操作∪下闭合,则L1∪L2将是正则语言。但是如果RL在∩下不封闭,那并不意味着L1∩L2不会是RL。
对于要在操作下关闭的类,它必须适用于该类中的所有语言。所以,如果一个类在一个操作下没有被关闭,我们就不能说这个操作的结果语言的类——它可能属于也可能不属于操作数语言的类。
简而言之,闭包属性是适用的,只有当语言在操作下被关闭时才适用。
现在让我们证明常规语言在互补操作下是封闭的-
问题
让两组的互补运算(COR)定义为-
COR(A,B)={x:x∉Aorx∉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。
然后DFAsM1的补码=(Q1,∑,δ1,q0,Q1−F1)和M2的补码=(Q2,∑,δ2,p0,Q2−F2)接受A的补码和B的补码。
因此,{x:x∉A}和{x:x∉B}是正则的。
那么根据上一题的结果,我们知道正则语言族在有限联合下是封闭的。
因此,我们得出结论,COR(A,B)是正规的