4

给定 L1 和 L2(不规则)上下文无关语言 - L1 U L2 是否可能是规则的?

我知道这是可能的,但我找不到一个例子来说明这一点。很想得到一些帮助。

4

1 回答 1

7

两个 CFL 的联合可以是规则的吗?

给定和上下文无关(但不是常规)语言,两者的结合是否有可能是常规的?L1L2L1 ∪ L2

是的可能!

假设,第一语言 L 1是:

L 1 : { | 其中}anbmn = m

语言 L 1是 CFL 但不是常规语言。L 1语言的 另一种书写方式是. 我认为这是在任何正式语言教科书中都可以找到的 CFL 最狡猾的例子之一。anbn

第二语言 L 2是:

L 2 : { | 其中}anbmn ≠ m

L 2再次是 CFL,但不是常规的。基本上 L 2是 L 1的补语.

现在,L 1和 L 2的并集是:

大号:{ | 和值没有限制}anbmnm

Language L=是一种正则语言, is的正则表达式。L1 ∪ L2La*b*

所以提示是补码 CFL 的联合是规则的。

注意:上下文无关语言在联合操作下是封闭的,因此两个 CFL 的联合始终是 CFL(可以是常规语言,因为常规语言类是 CFL 类的子集),但它不能是非 CFL,例如 CSL .

在评论的基础上添加:

两个 CFL 的交点可以是规则的吗?

给定和上下文无关(但不是常规)语言,两者的交集是否有可能是常规的?L1L2L1 ∩ L2

是的可能!

假设,第一语言 L 1是:

L 1 : { | 其中}anbmn = m

第二语言 L 2是:

L 2 : { | 其中}anbmn <= 3 or n ≠ m

Language L= =是一个有限集,因此也是一个常规集L1 ∩ L2{ab, aabb, aaabbb}

于 2014-01-19T09:51:44.107 回答