数据结构
网络
关系型数据库管理系统
操作系统
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+ 次查看
