
- 自動機理論教程
- 自動機理論 - 首頁
- 自動機理論 - 入門
- 自動機理論 - 歷史
- 自動機理論 - 應用
- 自動機理論術語
- 自動機中字串的基礎知識
- 自動機的集合論
- 語言和文法
- 計算理論中的文法
- 由文法生成的語言
- 喬姆斯基文法分類
- 有限自動機
- 確定性有限自動機 (DFA)
- 非確定性有限自動機 (NFA)
- 從NFA到DFA的轉換
- DFA的最小化
- Moore機與Mealy機
- DFA的補集
- 正則表示式
- 自動機中的正則表示式
- 自動機中的Arden定理
- 將正則表示式轉換為有限自動機
- 正則文法的泵引理
- 計算理論中的正則集
- 上下文無關文法
- 上下文無關文法 (CFG)
- 上下文無關文法中的二義性
- 上下文無關語言的閉包性質
- 簡化上下文無關文法
- 喬姆斯基正規化 (CNF)
- 格雷巴赫正規化 (GNF)
- 上下文無關文法的泵引理
- 下推自動機
- 下推自動機 (PDA)
- 下推自動機的接受
- 由CFG構造PDA
- 下推自動機和語法分析
- 圖靈機
- 圖靈機 (TM) 基礎知識
- 圖靈機接受的語言
- 多磁帶圖靈機
- 多軌跡圖靈機
- 非確定性圖靈機
- 半無限帶圖靈機
- 線性界限自動機 (LBA)
- 可計算性和不可判定性
- 圖靈語言的可判定性
- 不可判定語言
- 圖靈機停機問題
- 計算理論中的Rice定理
- Post對應問題 (PCP)
- 自動機理論資源
- 自動機理論 - 快速指南
- 自動機理論 - 資源
- 自動機理論 - 討論
CFL閉包性質
上下文無關語言在以下方面是封閉的:
- 並集
- 連線
- Kleene星號運算
並集
設L1和L2為兩個上下文無關語言。則L1 ∪ L2也是上下文無關的。
示例
設L1 = { anbn , n > 0}。對應的文法G1將具有P: S1 → aAb|ab
設L2 = { cmdm , m ≥ 0}。對應的文法G2將具有P: S2 → cBb| ε
L1和L2的並集,L = L1 ∪ L2 = { anbn } ∪ { cmdm }
對應的文法G將有額外的產生式S → S1 | S2
連線
如果L1和L2是上下文無關語言,則L1L2也是上下文無關的。
示例
語言L1和L2的並集,L = L1L2 = { anbncmdm }
對應的文法G將有額外的產生式S → S1 S2
Kleene星號
如果L是上下文無關語言,則L*也是上下文無關的。
示例
設L = { anbn , n ≥ 0}。對應的文法G將具有P: S → aAb| ε
Kleene星號L1 = { anbn }*
對應的文法G1將有額外的產生式S1 → SS1 | ε
上下文無關語言在以下方面不是封閉的:
交集 - 如果L1和L2是上下文無關語言,則L1 ∩ L2不一定是上下文無關的。
與正則語言的交集 - 如果L1是正則語言,L2是上下文無關語言,則L1 ∩ L2是上下文無關語言。
補集 - 如果L1是上下文無關語言,則L1’可能不是上下文無關的。
廣告