CFG

非上下文无关语言

若A是CFL,则存在数p(pumping length),使得A中任何一个长度不小于p的字符串s都能被划分为5段 $s=uvxyz$ 且满足下述条件:

  • 对于每一个 $i\geq 0$,$u v^i x y^i z \in A$
  • $|vy| > 0$ (保证v或y不是空串,否则定理自动成立,和正则语言的泵引理一样了)
  • $|vxy| \leq p$

能使用正则语言写出来或者DFA判别的就是正则语言
能使用上下文无关语言写出来或者PDA判别的就是上下文无关语言
剩下的都是其他语言
正则语言和上下文无关语言可以使用泵引理判假,即所有正则语言、上下文无关均符合他们的泵引理,但是不是所有符合泵引理的都是CFG或者CFL

正则语言包含上下文无关语言

在一个语言 A 中构建一个足够长的字符串 s,那么 s 就可以通过 A 对应的语法 G 来 parse 成一个 parse tree。所谓足够长的意思是,这个 parse tree 上会有一些足够长的从树根到叶的路径,根据鸽笼原理,这个路径上某些 non-terminal symbol,比如 N 会出现不止一次。你把子节点上的一个 N 替换成一个根节点上同构的 N,就相当于把字符串中间的某些部分重复了,这样 pumping 出来的新字符串依然符合其语法,也即依然在语言 A 中。

即,若 v 由完成 n 次入栈循环的路径标记,y 由完成 m 次出栈循环的路径标记,那么由于 m 次出栈循环刚好可以将 n 次入栈循环入栈的符号出栈,则类似的断言对 mi 及 ni 也成立。因此 v 与 w 可重复相同多的次数而所得到的字符串依旧在 A 中。

证明语言 $L = {a^i b^i c^i|i\geq 0}$ 不是上下文无关的.

Proof.

假设 L 是CFL,设 L 的泵长度为 p。根据泵引理,这个p一定存在。

取字符串 $s = a^p b^p c^p$,显然有:

  • $|s| \geq p$

  • s 属于 L

泵引理称s能够被抽取,但是我们证明这是不可能的,也就是要证明不管怎么把s划分成uvxyz,总要违反泵引理中的一个条件。

P108

https://blog.csdn.net/shulianghan/article/details/110631657

Author

preccrep

Posted on

2021-10-27

Updated on

2021-11-03

Licensed under

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments

You forgot to set the shortname for Disqus. Please set it in _config.yml.
You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.