每个RL也是CFL.但是,无限次的CFL是不正常的. CFL中存在的一个功能,使它们太复杂,无法成为常规的平衡对象：括号,开始块等.几乎所有的编程语言都是CFL. CFL可以通过所谓的下推自动机被有效地识别,这本质上是一个粘贴了NPC的NFA.堆栈根据需要增长到很大,因此它不再是有限自动机.实际编程语言的解析器几乎都是下推自动机的变体.
考虑使用反引号的正则表达式
^(b*a)\1$
换句话说,这表示一些n的长度为2n的字符串,其中第n个和第2n个字符都是a,所有其他字符都是b.这是一个非常规的CFL的完美示例.你可以用另外一种很酷的形式语言工具来证明这一点,称之为抽象引理.
这正是为什么回参考引起问题！它们允许表示不常规语言的“正则表达式”.因此,没有NFA或DFA无法识别它们.
但是,等等,这甚至比我已经这么远了.考虑
^(b*a)\1\1$
我们现在有一个长度为3n的字符串,其中第n个,第2n个和第3个元素是a,所有其他元素都是b.还有另外一种抽搐法的风味,可以证明这种语言太复杂,不能成为CFL！没有下推自动机可以识别这个.
后面的引用允许这些增强的正则表达式表示Chomsky层次结构上的三个语言：语境敏感语言.大致来说,识别CSL的唯一方法是检查所有长度相同的字符串(至少如果P！= NP,但是对于所有实际目的都是如此,并且完全不同).这些字符串的数量在您匹配的字符串的长度上是指数的.
这就是为什么需要搜索正则表达式匹配器的原因.你可以非常聪明的设计搜索的方式.但是,总是会有一些投入使它花费指数时间.
所以我同意你引用的论文的作者.可以编写完美无瑕的正则表达式,没有后退参考,几乎所有输入都将被高效地识别,但是存在导致Perl或Java或Python正则表达式匹配器的一些输入,因为它是一个回溯搜索 – 要求数百万几年完成比赛.这太疯狂了.你可以有一个脚本是正确的,工作正常多年,然后锁定一天只是因为它绊倒了一个坏的输入.假设正则表达式被掩埋在你正在骑的飞机上的导航系统的消息解析器中
编辑
根据要求,我将描述如何使用抽水引理来证明语言a ^ k b a ^ k b不是常规的.这里^ k是重复k次的缩写. PL表示必须存在正整数N,使得长度至少为N的常规语言中的每个字符串必须具有R S T的形式,使得R S ^ k T也在所有自然k的语言中.这里R,S,T是字符串,S可能不为空.
PL的证明取决于每个常规语言对应于一些DFA的事实.这个DFA的接受输入长于其状态数(相当于引文中的L)必须使其“循环：”重复一个状态.调用这个状态X.机器消耗一些字符串R从起始到X,然后S循环回X,然后T到达接受状态.那么,在输入中添加S的额外副本(或者删除S)只对应于从X返回到X的不同数量的“循环”.因此,还将接受带有附加(或删除的)S副本的新字符串.
由于每个RL都必须满足PL,所以证明语言不是常规的证明,表明它与PL相矛盾.对于我们的语言,这并不难.假设你试图说服我的语言L = a ^ k b a ^ k b满足PL.因为这样做,你必须能够给我一些N值(见上文)：一个假设的DFA中识别L的状态数.在这一点上,我会说：“好吧,普通人先生,考虑字符串B = a ^ N ba ^ N b.“如果L是常规的,B必须使这个DFA(不管它是什么样的)在前N个字符中循环,这必须全部为！所以循环(上面的字符串S)也包括所有的.有了这个,我可以立即显示你对L的正常要求是假的.我只是选择第二次绕圈.这将导致您的这个假设的DFA接受一个新的字符串a ^ M b a ^ N b,其中M> N,因为我添加了上半部分.哎哟!这个新的字符串不在L中,所以PL毕竟不是真的.由于我每次都可以做这个技巧,无论你提供什么,PL都不能持有L,而L不能一直是正常的.
由于它不是常规的,所以Kleene的定理告诉我们,没有描述它的DFA或FA和“纯粹”正则表达式.
背面参考的证明允许甚至没有上下文的语言具有非常相似的环,但需要下推自动机的背景,我不会在这里给出. Google将提供.
注意：这两个都没有证明后退参考使得NP完整.他们只是以非常严格的方式来说,反驳引用了纯正则表达式的真正复杂性.它们允许任何无限制存储器的机器无法识别的语言,也不允许只有无限大的LIFO存储器.我会把NP的完整性证明给别人.
