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

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

Read more
You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.