数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学解释正则语言与上下文无关语言的并集和交集
我们知道，有限自动机 (FA) 接受的语言称为正则语言，而下推自动机 (PDA) 接受的语言称为上下文无关语言 (CFG)。
上下文无关语言在并集下的封闭性
CFL 是上下文无关语言的简写。这里的 CFL 定义如下：
G = (V, Σ, R, S) 使得 L(G) = L(G1) ∪ L(G2)
因此，
V = V1 ∪ V2 ∪ {S}（三个集合不相交）
Σ = Σ1 ∪ Σ2
R = R1 ∪ R2 ∪ {S → S1|S2}
正则语言与CFG的并集
如果所有正则语言都是上下文无关的，那么两者的并集也是上下文无关语言。
示例
设 L1 = {0*1*} 是一个正则语言，并且
L2 = {0^n1^n |n>=0} 是一个上下文无关语言
设 L=L1 ∪ L2 是这两个语言的并集。问题中给出 L = {0*1*} 是一个正则语言。
我们知道每个正则语言都是上下文无关的。因此，我们可以说两个语言的并集总是上下文无关语言。因为两个上下文无关语言的并集是一个上下文无关语言。
证毕。
正则语言与CFG的交集
我们知道所有正则语言都是CFG的子集。
并集运算很容易理解，我们也证明了正则语言与上下文无关语言的并集产生一个上下文无关语言。
现在来看交集：
正则语言和上下文无关语言的交集总是产生一个上下文无关语言。
示例
L1 = {0*1*} 是一个正则语言，并且
L2 = {0^n1^n |n>=0} 是一个CFL
两个语言的交集如下：
L= L1 ∩ L2
结果如下：
L={0^n1^n | n>=0} 这是一个上下文无关语言。
因此，最终得出结论：正则语言和上下文无关语言的交集产生一个上下文无关语言。
更新于：2021年6月15日
2K+ 次浏览
广告