给定 L1 和 L2(不规则)上下文无关语言 - L1 U L2 是否可能是规则的?
我知道这是可能的,但我找不到一个例子来说明这一点。很想得到一些帮助。
给定 L1 和 L2(不规则)上下文无关语言 - L1 U L2 是否可能是规则的?
我知道这是可能的,但我找不到一个例子来说明这一点。很想得到一些帮助。
给定和上下文无关(但不是常规)语言,两者的结合是否有可能是常规的?
L1
L2
L1 ∪ L2
是的可能!
假设,第一语言 L 1是:
L 1 : { | 其中}
anbm
n = m
语言 L 1是 CFL 但不是常规语言。L 1语言的 另一种书写方式是. 我认为这是在任何正式语言教科书中都可以找到的 CFL 最狡猾的例子之一。anbn
第二语言 L 2是:
L 2 : { | 其中}
anbm
n ≠ m
L 2再次是 CFL,但不是常规的。基本上 L 2是 L 1的补语.
现在,L 1和 L 2的并集是:
大号:{ | 和值没有限制}
anbm
n
m
Language L
=是一种正则语言, is的正则表达式。L1 ∪ L2
L
a*b*
所以提示是补码 CFL 的联合是规则的。
注意:上下文无关语言在联合操作下是封闭的,因此两个 CFL 的联合始终是 CFL(可以是常规语言,因为常规语言类是 CFL 类的子集),但它不能是非 CFL,例如 CSL .
在评论的基础上添加:
给定和上下文无关(但不是常规)语言,两者的交集是否有可能是常规的?
L1
L2
L1 ∩ L2
是的可能!
假设,第一语言 L 1是:
L 1 : { | 其中}
anbm
n = m
第二语言 L 2是:
L 2 : { | 其中}
anbm
n <= 3 or n ≠ m
Language L
= =是一个有限集,因此也是一个常规集。L1 ∩ L2
{ab, aabb, aaabbb}