数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学如何证明正则语言在补运算下是封闭的？
封闭性是一种理解当我们对同一类别的两个语言进行运算时，结果语言的类别的方法。
这意味着，假设L1和L2属于正则语言，如果正则语言在∪运算下是封闭的，那么L1∪L2将是一个正则语言。但是，如果RL在∩运算下不是封闭的，这并不意味着L1∩L2不会是RL。
对于一个类别来说，要在某个运算下是封闭的，它必须对该类别中的所有语言都成立。因此，如果一个类别在某个运算下不是封闭的，我们不能对该运算的结果语言的类别做任何断言——它可能属于也可能不属于操作数语言的类别。
简而言之，封闭性只有在语言在某个运算下是封闭的情况下才适用。
现在让我们证明正则语言在补运算下是封闭的：
问题
设两个集合的补运算(COR)定义为：
COR(A, B) = {x : x ∉ A 或 x ∉ B}，我们需要证明正则语言在COR运算下是封闭的。
在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。
那么DFA M1的补集 = (Q1, ∑, δ1, q0, Q1 − F1) 和 M2的补集 = (Q2, ∑, δ2, p0, Q2 − F2) 接受A的补集和B的补集。
因此，{x : x ∉ A} 和 {x : x ∉ B} 是正则的。
然后根据上一个问题的结论，我们知道正则语言族在有限并集下是封闭的。
因此，我们得出结论，COR(A,B) 是正则的。
更新于：2021年6月11日
3K+ 次浏览
广告