两个(不规则)上下文无关语言的联合会产生常规语言吗？

Question

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

我知道这是可能的,但我无法找到一个显示的例子.很想获得一些帮助.

Answer 1

两个CFL联盟可以定期吗？

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

是的可能!

假设,第一语言L ₁是:

L ₁:{ | 哪里}anbmn = m

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

第二语言L ₂是:

L ₂:{ | 哪里}anbmn ≠ m

L ₂也是CFL,但不是常规.基本上L ₂是L _1的补语.

现在,L ₁和L _2的联合是:

L:{ | 没有限制和值}anbmnm

语言L= 是一个普通的语言和正则表达式是.L1 ∪ L2La*b*

所以提示补充CFL的联合是常规的.

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

在评论的基础上添加:

两个CFL的交叉点可以定期吗？

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

是的可能!

假设,第一语言L ₁是:

L ₁:{ | 哪里}anbmn = m

第二语言L ₂是:

L ₂:{ | 哪里}anbmn <= 3 or n ≠ m

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