type
status
date
slug
summary
tags
category
icon
password

目录

目录鸽笼原理（抽屉原理）泵引理介绍原理定义泵引理的应用
💡
「泵引理 Pumping Lemma」是一个用于判断一个语言是否是正规式的定理。
在介绍泵引理之前，首先要介绍鸽笼原理，这是泵引理的理论基础。

鸽笼原理（抽屉原理）

通俗解释鸽笼原理。
桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。

泵引理介绍

原理

假设一个正规式语言可以被DFA表示，设这个状态机为M，M有p个状态。
我们从这个正规式语言中选取一个长度为p的字符串s，且s可以被划分成xyz三部分。
dfa在单状态性下，每读取一个字符，状态就会转移，因此s中的p个字符在状态机中移动p次，需要p+1个状态，但状态机中只有p个状态，因此根据鸽笼原理，其中有两次状态转移是在同一个状态进行的，也就是至少有一个环。我们设这个状态为1，起始为0，末尾为2。
从状态0 到1设为x，1的环设为y，1到2设为z。此时泵引理的三个条件被满足：
  • 条件1：，因为y无论几个环最终都会回到1状态，然后通过z字符串被状态机接受。
  • 条件2：，鸽巢原理可得。
  • 条件3：，因为，xy是s的子串，显然成立。

定义

假设是正则语言，则存在整数，对任意字符串（其中n为泵的长度，可以理解为正则语言等效的极小化dfa的状态个数），可以将w写成的形式，使得以下说法均成立。

泵引理的应用

💡
证明：不能被正规式描述。
利用反证法，假设L是正规的。
根据泵引理，存在一个正整数p，使得对于L中任何长度至少为p的字符串w，都可以将其分解为xyz，并满足上述三个条件。
考虑字符串，其长度显然大于p。根据泵引理，我们可以将s分解为xyz，其中∣xy∣≤p且∣y∣≥1。
由于∣xy∣≤p，y只能包含a字符（因为s的前p个字符都是a）。因此，。
现在，考虑字符串。根据泵引理，也应该属于L。但是，包含，其中，因此的形式不是，这与相矛盾。
因此，我们的假设”L是正规的”是错误的。所以，语言不能被正规式描述。
 
notion快速搭个人博客（真的超快！）LLVM与Clang的发展史