資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究證明CFL在並集和閉包下是封閉的，但在交集下不是封閉的？
CFL指的是計算理論（TOC）中的上下文無關語言。現在讓我們瞭解CFL如何在並集下封閉。
CFL在並集下封閉
如果L1和L2是CFL，則L1 U L2也是CFL。
假設L1和L2由上下文無關文法（CFG）生成。
G1=(V1,T1,P1,S1)和G2=(V2,T2,P2,S2)，不失一般性地將G1的每個非終結符下標為a1，將G2的每個非終結符下標為a2（以便V1∩V2=φ）。
後續步驟使用完全來自G1或G2的產生式。
因此生成的每個單詞要麼是L1中的單詞，要麼是L2中的單詞。
示例
假設L1是迴文，定義為
S->aSa|bSb|a|b|^
假設L2是{anbn|n>=0}，定義為−
S->aSb|^
則並集語言定義為−
S->S1|S2
S1->aS1a|bS1b|a|b|^
S2->aS2b|^
CFG在克萊尼星號下是封閉的
現在，讓我們瞭解CFG如何在星號下封閉。
證明
如果L1是CFL，則L1*是CFL。
假設L1由CFG G1=(V1,T1,P1,S1)生成，不失一般性地將G1的每個非終結符下標為a1。
定義CFG G生成L1*為−
G=(v1 U {S}, T1, P1 U {S->S1S{^},S})
生成的每個單詞要麼是^，要麼是L1中相同單詞的序列。
L1*中的每個單詞都可以由G生成。
示例
假設L1是{anbn|n>=0}，定義為S->aSb|^
則L1*生成為
S->S1S|^
S1->aS1b|^
CFG在交集下不是封閉的
現在讓我們瞭解CFG如何在交集下不是封閉的。
證明
如果L1和L2是CFL，則L1∩L2可能不是CFL。
L1={anbnam|n,m>=0}由CFG生成−
S->XA
X->aXb|^
A->Aa|^
L2-{anbmam|n,n>=0}由CFG生成−
S->AX
X->aXb|^
A->Aa|^
L1∩L2 ={anbnan|n>=0}，它不是CFL。
3K+ 次檢視
