上下文无关语言
上下文无关语言
关闭属性
与上下文无关的语言具有以下闭包属性。一组是关闭在一个操作下,如果在给定的集合上执行操作总是产生同一集合的成员。这意味着,如果这些封闭操作中的一个应用于上下文无关的语言,其结果也将是一个上下文无关的语言。
- 联盟:上下文无关的语言在联盟操作。这意味着如果 那么这两种语言都与上下文无关吗 也是一种上下文无关的语言。
这里证明了上下文无关的语法在联合下是封闭的。[2]
让 而且 由上下文无关的语法生成, 而且 ,分别。
在不丧失一般性的情况下,将每个非终结符标下标 与一个 的每个非结束符 与一个 这样 .
定义CFG, ,生成 如下: .
- 连接:如果 那么这两种语言都与上下文无关吗 也是与上下文无关的。字符串的连接定义如下: .
这里证明了上下文无关的语法在连接下是封闭的。这个证明类似于并包证明。
让 而且 由上下文无关的语法生成, 而且 ,分别。
在不丧失一般性的情况下,将每个非终结符标下标 与一个 的每个非结束符 与一个 这样 .
定义CFG, ,生成 如下: .
每一个字, 生成是一个词 后面还有一个单词 ,这是串联的定义。
- 克林星号:如果 那么,这是上下文无关的语言吗 也是与上下文无关的。Kleene星号可以重复它所附加的字符串或符号任意次数(包括0次)。Kleene星号基本上执行一个字符串与其本身的递归连接。例如, 等等。我们已经证明了cfl在串联下是闭合的。
上下文无关语言不在补语下闭合或十字路口.
如果CFL在交集下是关闭的,那么就会有CFL违反上下文无关语言的抽运引理(更多细节见下一节),而这是不可能的。
以两种上下文无关的语言为例 而且 .的交集 而且 , 我们将在下面的上下文无关语言的引理中看到,它不是一个上下文无关的语言。
为了说明CFL在补语下是不闭合的,我们将使用矛盾,交集的结果,和德摩根定律.
为了避免矛盾,假设 上下文无关的语言是否 是一种上下文无关的语言。
我们知道cfl在工会和德摩根定律下是关闭的:
可以改写为:
这是:
因为我们假设 而且 如果cfl导致了一个错误的陈述,我们知道cfl在补充下并没有关闭。
上下文无关语言的抽水引理
要证明某种语言不是一种与上下文无关的语言,需要找到一种与上下文无关的语法来描述这种语言,或者使用另一种证明技术(尽管泵注引理是最常用的一种)。用来证明一门语言不是与上下文无关的一个常见引理是上下文无关语言的引理抽取.
的抽取上下文无关语言的引理说明如果一种语言 是否与上下文无关,是否存在某个整数泵送长度 这样每一个字符串 长度为 或多个符号, ,可以写成 在哪里 的子字符串 这样:
所有与上下文无关的语言都是“可泵送的”,这意味着泵送引理约束对所有与上下文无关的语言都成立。如果一门语言不是可泵送的,那么它就不是一门与上下文无关的语言。然而,如果一门语言是可泵送的,它就不一定是上下文无关的语言。因为常规语言集包含在与上下文无关的语言集中,所以所有常规语言也必须是可泵送的。
本质上,抽运引理包含任意长的字符串 是否可以在不产生不属于该语言的新字符串的情况下进行泵送 .
要证明一种语言不是与上下文无关的,请使用反证法还有抽水引理。建立一个证明来证明 与上下文无关,并表明泵浦引理约束的矛盾发生在上面列出的三个约束中的至少一个。
基本上,上下文无关语言的泵注引理背后的思想是,为了成为上下文无关语言,语言必须遵守某些约束。您可以使用泵注引理来测试是否所有这些约束都适用于一种特定的语言,如果它们不适用,您可以矛盾地证明该语言不是与上下文无关的。
用抽水引理来证明 不是一种上下文无关的语言。[3]
为了避免矛盾,假设 是上下文无关语言。根据抽运引理,存在一个整数抽运长度 为 .我们需要一个字符串 的长度大于或等于 .当然 长于 ,所以我们选择这个作为 字符串。这 是在 因为它有 一个的, b的, c。
根据抽水引理, .字符串中有5个位置可以赋值 :
对于一些 .这意味着 只包含在a的部分。
对于一些 而且 在哪里 这意味着 段包含在a和b段的某个地方。
对于一些 .这意味着 完全包含在b的部分。
对于一些 而且 在哪里 这意味着 段包含在b和c部分的某个地方。
对于一些 .这意味着 仅仅包含在c的部分。
在这五种情况中,我们可以很容易地验证抽运引理的第三个约束,即 ,并不成立。换句话说,对于这五个选项中的任何一个 ,字符串 不能以一种方式抽运导致字符串具有相同数量的a、b和c(语言的定义) ).
让我们举一个简短的字符串示例 而且 .
在第一种情况下,a的个数会比b和c的个数多,这样产生的抽运字符串就不是 .如果我们泵送这个区域,我们会得到字符串aaaaaaaabbbbbccccc:一个字符串 一个的, b的, c。很明显,这在语言中并不存在。类似的证明可以检查第三和第五种情况,只泵b和c区域,分别,结果将是对称的。
对于第二种和第四种情况,我们做类似的操作。如果我们只在a和b区域的任何地方泵浦,我们将得到一个a和b比c多的结果字符串(对于第二种情况),以及b和c比a多的结果字符串(对于第五种情况)。对于第二种情况,如果我们取 而且 把a部分的最后一个a和b部分的前两个b,我们得到这个字符串:aaaaaabbbbbbbccccc -一个有6个a, 7个b和5个c的字符串。第五种情况有一个对称的例子。
在上面的例子中,why was 对于一些 , , 在哪里 的选项之一不包括在内 ?
抽运引理的第一个约束是 .因为字符串是 ,有 一个是,紧随其后 b是,紧随其后 c。如果 跨越a区域,b区域和c区域,它一定比 .例如,如果 只包括a区域的最后一个a,整个b区域,然后是c区域的第一个元素,它就会有长度 因此这是行不通的。
与其他计算模型的关系
任何可以生成的语言正则表达式可以由上下文无关的语法生成,但并非所有上下文无关的语言都是规则语言。我们还知道正则表达式和语言可以通过有限状态机(一个简单的计算模型)。
常规语言可以“跟踪”一件事,而上下文无关的语言最多可以“跟踪”两件事。例如,有一种常规语言可以生成所有具有偶数个0的字符串,但没有一种常规语言可以生成所有具有相等数量1和0的字符串——然而,上下文无关的语言可以做到这一点。但是,上下文无关语言或常规语言都不能为具有相同数量的a、b和c的所有字符串生成语言(请参阅上面部分中的抽水引理示例)。
有一种语法叫做上下文敏感的语法它们比常规语言和上下文无关的语言更强大(意味着它们可以生成可能需要更多内存的更复杂的语言)。
上下文无关语言由上下文无关语法描述,它可以由下推自动机.常规语言和有限状态机可以描述一些与上下文无关的语言,但不是全部。图灵机可以生成所有常规语言、所有上下文无关语言等等。
另请参阅
参考文献
- , J。乔姆斯基层次结构.检索自2016年6月13日https://en.wikipedia.org/wiki/Chomsky_hierarchy
- Cappello, P。第十七章:上下文无关语言.检索于2016年6月14日http://www.cs.ucsb.edu/~cappello/136/lectures/17cfls/slides.pdf
- ,。抽取上下文无关语言的引理.检索自2016年6月13日https://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages