正则语言与 CFL 的并集和交集
众所周知，有限自动机接受的语言称为正则语言，下推自动机接受的语言称为上下文无关语言但是，当涉及到这两种语言的并集或交集时，有些人发现很难分析交集是导致正则语言还是上下文无关语言。
首先要观察的是每一个正则语言其实都是上下文无关的，原因相当简单。一种称语言为正则的方法是通过设计它的等价有限自动机，或者换句话说，如果我们可以为一种特定的语言设计一个有限自动机，那么只有我们可以称那种语言为正则的，同样的存在于上下文无关的语言中，如果可以为一种特定的语言设计一个下推自动机，那么只有它被称为上下文无关的。
简单来说，下推自动机实际上是一个有限自动机，其内存为无限堆栈。你需要观察的是，有可能为一种特定的语言设计一个有限自动机，那么也有可能设计它的等价下推自动机。我们要做的只是不要使用里面的无限堆栈。就这么简单。观察这一点，最后你会发现，对于每一种常规语言，都有可能设计有限自动机，从而推下自动机。这就是为什么每种常规语言也可以称为上下文无关语言，或者换句话说，常规语言是上下文无关语言的子集。
正则语言与上下文无关语言的结合– 由于所有正则语言都是上下文无关的，因此两者的结合产生了上下文无关语言。但是借助一个例子来理解总是好的。 让我们取一种语言 L1 = {01}(常规)和 L2 = {0^n1^n |n > =0}(与上下文无关) 并让 L=L1 U L2，这将导致这两种语言的联合，即:
L = {01}这是常规语言，但由于每种常规语言都是上下文无关的。所以，我们可以说两者的结合总是导致上下文无关的语言。
正则语言与上下文无关语言的交集– 因为现在我们知道所有的正则语言都是上下文无关语言的子集，所以理解两者的并集没有问题，但是当我们再次谈论交集时，答案是上下文无关语言。是的，正则语言和上下文无关语言的交集总是导致上下文无关语言。
让我们再举一个上面的例子，其中 L1 和 L2 是相同的，但是现在让 l = L1∪L2，这将很容易产生与上下文无关的 L={0^n1^n | n > =0}。 你可以举更多这样的例子，验证常规语言和上下文无关语言的并集和交集总是产生上下文无关语言。
阅读下一篇文章–上下文无关语言的闭包属性
本文由 迪皮·瓦什尼 供稿。如果你喜欢 GeeksforGeeks 并想投稿，你也可以使用contribute.geeksforgeeks.org写一篇文章或者把你的文章邮寄到 contribute@geeksforgeeks.org。看到你的文章出现在极客博客主页上，帮助其他极客。
如果你发现任何不正确的地方，或者你想分享更多关于上面讨论的话题的信息，请写评论。
版权属于：月萌API www.moonapi.com，转载请注明出处
