我看到了这个问题,并对抽取引理是什么感到好奇(维基百科没有多大帮助).
我理解这基本上是一个理论证明,必须是真实的,以便语言在某个类中,但除此之外,我并没有真正得到它.
有人试图以非数学家/ comp sci博士学位理解的方式在相当精细的层面上解释它吗？
抽取引理是一个简单的证明,表明语言不规则,这意味着无法为它构建有限状态机.规范的例子是语言(a^n)(b^n).这是一种简单的语言,它只是任意数量的as,后跟相同数量的bs.所以字符串
ab aabb aaabbb aaaabbbb
等等都是语言,但是
aab bab aaabbbbbb
等不是.
为这些示例构建FSM非常简单:
这个将一直工作到n = 4.问题是我们的语言没有对n施加任何约束,而有限状态机必须是有限的.无论我添加到这台机器的状态有多少,有人可以给我一个输入,其中n等于状态数加一,我的机器将失败.因此,如果有一台机器可以读取这种语言,那么必须在某处设置一个循环来保持状态数量的有限.添加了这些循环:
我们语言中的所有字符串都将被接受,但是存在问题.在前四a秒之后,机器会丢失a已输入的数量,因为它保持相同的状态.这意味着在四次之后,我可以添加a任意数量b的字符串,而不添加任何s,仍然可以获得相同的返回值.这意味着字符串:
aaaa(a*)bbbb
与(a*)代表任意数量的aS,将全部由即使他们显然不是所有的语言机器被接受.在这种情况下,我们会说(a*)可以抽出字符串的一部分.有限状态机是有限的并且n没有界限这一事实保证了任何接受语言中所有字符串的机器必须具有这种属性.机器必须在某个时刻循环,并且在循环时可以抽取语言.因此,不能为此语言构建有限状态机,并且语言不规则.
请记住,正则表达式和有限状态机是等价的,然后替换a和b打开和关闭可以嵌入彼此的Html标签,你可以看到为什么不可能使用正则表达式来解析Html
它是一种旨在证明给定语言不能属于某一类的设备.
让我们考虑平衡括号的语言(意思是符号'('和')',并包括所有以通常含义平衡的字符串,而不包括所有字符串).我们可以使用泵浦引理来证明这不规律.
(语言是一组可能的字符串.解析器是我们可以用来查看字符串是否在语言中的某种机制,因此它必须能够区分语言中的字符串或外部字符串之间的区别如果有一个可以识别它的常规(或其他)解析器,区分语言中的字符串和不在语言中的字符串,则语言是"常规"(或"无上下文"或"上下文敏感"或其他).语言.)
LFSR Consulting提供了很好的描述.我们可以将常规语言的解析器绘制为有限的框和箭头集合,箭头表示字符和连接它们的框(充当"状态").(如果它比那更复杂,它不是常规语言.)如果我们可以得到一个比盒子数更长的字符串,这意味着我们不止一次地通过一个盒子.这意味着我们有一个循环,我们可以根据需要多次循环.
因此,对于常规语言,如果我们可以创建一个任意长的字符串,我们可以将它分成xyz,其中x是我们需要到循环开始的字符,y是实际的循环,z是我们的任何东西需要在循环后使字符串有效.重要的是x和y的总长度是有限的.毕竟,如果长度大于盒子的数量,我们显然在做这个时经历了另一个盒子,所以有一个循环.
因此,在我们平衡的语言中,我们可以从编写任意数量的左括号开始.特别是,对于任何给定的解析器,我们可以编写更多的左侧parens,而不是有框,因此解析器无法分辨出有多少左侧的parens.因此,x是一些左边的parens,这是固定的.y也是一些左边的parens,这可以无限增加.我们可以说z是一些正确的parens.
这意味着我们可能有一个由43个左侧parens和43个右侧parens识别的字符串,但解析器无法从44个左侧parens和43个右侧parens字符串中识别出来,这不是我们的语言,所以解析器无法解析我们的语言.
由于任何可能的常规解析器都有固定数量的框,我们总是可以编写更多的左边的parens,并且通过抽取引理,我们可以以解析器无法分辨的方式添加更多的左边的parens.因此,平衡括号语言不能由常规解析器解析,因此不是正则表达式.
以外行人的术语来说很困难,但基本上正则表达式中应该有一个非空的子字符串,可以重复多次,而整个新单词对语言仍然有效.
在实践中,泵浦引理不足以证明语言是正确的,而是作为一种通过矛盾进行证明的方法,并通过显示泵浦引理来表明语言不适合语言类(常规或无上下文)不适合它.
京公网安备 11010802040832号 | 京ICP备19059560号-6 