資料結構
網路
關係資料庫管理系統 (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+ 次瀏覽
廣告