外行术语中的泵送引理是什么?

抽水引理是一个简单的证明,表明一种语言是不规则的,这意味着不能为它建立一个有限状态机。典型的例子是语言 (a^n)(b^n) . 这是一种简单的语言 a s、 后面跟着相同数量的 b s、 所以琴弦

ab
aabb
aaabbb
aaaabbbb

等等都是用语言表达的,但是

aab
bab
aaabbbbbb

等等都不是。

为以下示例构建FSM非常简单:

这个可以一直工作到n=4。问题是我们的语言没有对n施加任何约束,而有限状态机必须是有限的。不管我给这台机器添加多少状态,有人可以给我一个输入,其中n等于状态数加一,我的机器就会失败。因此,如果有一台机器可以用来阅读这种语言,那么在那里的某个地方一定有一个循环来保持状态的数量是有限的。添加这些循环后:

一 s、 机器数不清有多少 一 s被输入是因为它保持不变的状态。也就是说,四点之后,我可以再加多少 一 就像我想要的那样,不加任何东西 b

aaaa(a*)bbbb

具有 (a*) 一 s、 所有的都会被机器接受,即使它们显然不是所有的语言。在这种情况下,我们可以说 可以泵送。有限状态机是有限的而n是不有界的这一事实保证了接受语言中所有字符串的任何机器都必须具有这个属性。机器必须在某个点循环,在它循环的点上,语言可以被泵送。因此,不能为这种语言建立有限状态机,而且这种语言是不规则的。

记住这一点 Regular Expressions and Finite State Machines are equivalent ,然后更换 一 和 b 通过打开和关闭Html标记,可以相互嵌入,您可以看到为什么 it is not possible to use regular expressions to parse Html

让我们考虑一下平衡圆括号的语言(意思是符号“(”and“)”,包括在通常意义上平衡的所有字符串,没有不平衡的字符串)。我们可以用泵引理来证明这是不规则的。

(语言是一组可能的字符串。解析器是某种机制,我们可以用来查看字符串是否在语言中,因此它必须能够区分语言中的字符串和语言之外的字符串之间的区别。如果有一个常规的(或其他)解析器可以识别一种语言,并区分语言中的字符串和非语言中的字符串,那么该语言就是“常规”(或“上下文无关”或“上下文相关”或其他任何东西)

LFSR咨询公司提供了很好的描述。我们可以为一种常规语言绘制一个解析器,它是由方框和箭头组成的有限集合,箭头代表字符,方框连接字符(充当“状态”)。(如果它比这更复杂的话,它不是一种常规语言)如果我们可以得到一个比盒子数量长的字符串,那就意味着我们不止一次地穿过一个盒子。这意味着我们有一个循环,我们可以循环多次。

因此,对于常规语言,如果我们可以创建一个任意长的字符串,我们可以将它分成xyz,其中x是到达循环开始所需的字符,y是实际的循环,z是在循环之后使字符串有效所需的任何内容。重要的是x和y的总长度是有限的。毕竟,如果长度大于盒子的数量,我们显然在做这个的时候,又经历了另一个盒子,所以有一个循环。

所以,在我们的平衡语言中,我们可以从写任意数量的左括号开始。特别是,对于任何给定的解析器,我们可以编写比方框更多的左paren,因此解析器无法判断有多少个左paren。因此,x是左帕伦斯数,这是固定的。y也是一些左帕伦数,这可以无限增加。我们可以说z是右帕伦数。

这意味着我们的解析器可能识别出一个43个左parens和43个right parens字符串,但是解析器无法从44个left parens和43个right parens字符串中分辨出来,这不是我们的语言,所以解析器无法解析我们的语言。

在 实践

pumping引理建立了一种方法,通过该方法可以从语言中选择一个“单词”,然后对其进行一些更改。这个定理指出,如果语言是规则的,这些变化应该产生一个仍然来自同一种语言的“单词”。如果你想到的这个词不在这门语言中,那么这门语言本来就不可能是正规的。

现在假设你有一个字符串,它被有限自动机识别,它的长度足以“超过”自动化的内存,也就是说,其中的状态必须重复。然后有一个子串,其中自动机在子串开头的状态与子串末尾的状态相同。由于读取子字符串不会改变状态,因此它可能会被删除或复制任意次数,而不会让自动机更聪明。所以这些修改过的字符串也必须被接受。

根据定义,正则语言是由有限状态自动机识别的语言。把它想象成一个迷宫:状态是房间,过渡是房间之间的单向走廊,有一个初始房间和一个出口(最终)房间。正如“有限状态自动机”这个名字所说,房间的数量是有限的。每次你沿着走廊旅行时,你都会把写在走廊墙上的信草草写下来。如果你能找到一条从最初的房间到最后一个房间的路径,穿过标有字母的走廊,并按照正确的顺序,就可以识别出一个单词。

more complex .

不是 在某个班级里。

例如,考虑一种正则语言(regexp、automata等),其中包含无限数量的字符串。在某个时刻,正如starblue所说,内存耗尽是因为字符串对于自动机来说太长了。这意味着必须有一个字符串块,而自动机不能告诉你有多少个副本(你在一个循环中)。所以,任何数量的子字符串的副本在字符串中间,你仍然是在语言。

这意味着,如果您的语言没有此属性,即有足够长的字符串 子串,你可以重复任何次数,但仍然是语言,那么语言是不规则的。

我 = 一 ^{n n}

现在试着将有限自动机可视化为上面的语言 n

如果 n =1,字符串 w ab型 . 在这里我们可以做一个没有循环的有限自动机 如果 =2,字符串 w ^{2 2} . 在这里我们可以做一个没有循环的有限自动机

n = p ,字符串 w ^p b 第一阶段,它需要一系列输入,然后进入第二阶段。同样地,从第二阶段到第三阶段。我们把这些阶段称为 十 是的 和 z .

有一些观察结果

1. 一定地 十 z
2. 现在我们必须弄清楚 是的 :
   • 一 : 是的
   • 案例 只能包含“b”
   • 案例 : 是的 可能包含“a”和“b”的组合

所以有限自动机的状态是 是的 应该能够接受输入'a'和'b',也不应该采取更多的a's和b's,这是不可数的。

1. 中频阶段 是的 只取一个“a”和一个“b”,那么需要两个状态
2. 如果需要两个'a'和一个'b',则需要三个状态,不使用out循环 等等。。。。

所以舞台的设计 是的 完全是无限的。我们只能通过放置一些循环使其成为有限的,如果我们设置循环,有限自动机可以接受其他语言 我 = 一 b

这不是这样的解释,但很简单。 对于a^n b^n,我们的FSM的构建方式应该是b必须 a的数量已经被解析,并且将接受相同数量的b。FSM不能简单地做这样的事情。