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’可能不是上下文無關的。

廣告