4.1 泵引理

泵引理(pumping lemma)用于证明语言不是规则语言。它是一个重复不必要条件。

定理:$L$ 是规则语言。则存在 $n$ 满足:只要字符串 $w$ 的长度 $|w|\geq n$,就能将 $w$ 分为三段,$w = xyz$,使得:

  1. $y \ne \varepsilon$
  2. $|xy|\leq n$
  3. 对任意 $k \geq 0$,$xy^k z$ 属于 $L$

我们可以通俗地理解:规则语言只能存放有限个状态,所以只要一个字符串足够长,肯定要耗尽所有状态,折回去使用已经用过的状态,从而,字符串的中间 $y$ 必可重复。

4.2 规则语言的封闭性

如果两个语言是规则的,则对二者执行特定运算之后得到的语言同样是规则的。

这些运算包括:

  1. 交并补差
  2. 反转、闭包 (*)、连接
  3. 同态和逆同态

4.3 规则语言的判定性质

4.4 自动机的等价性和最小化

对于状态 $p,q$,如果对于任意输入串 $w$,$\hat {\delta}(p,w)$ 是接受状态和 $\hat {\delta}(q,w)$ 二者互为充要条件,说明 $p,q$ 状态等价。否则说 $p,q$ 状态可区分

就是说,如果 $p,q$ 对于任意输入表现的行为完全一致(要么最终都接受,要么最终都不接受),那么 $p,q$ 等价。

4.4.1 填表算法

这是一种常见的递归算法,用于寻找 DFA 的可区分状态对。

例子:

image-20210615224815032

有八个状态,可以形成 $7\times 8=56$ 个状态对。所以列表如下:

image-20210615225659097

由于 C 是唯一的接受状态,所以涉及 C 的状态是可区分的:

image-20210615232003794

假定输入串结尾是 0,则只能从 F,D 到达 C,所以 F,D 各自与其它状态都是可区分的:

image-20210615232716346

假定输入串结尾是 1,则只能从 B,H,C 到达 C,所以 B,H 各自与其它状态都是可区分的:

image-20210615232826955

对 A,G 输入 1,分别到达 E,F。由于 E,F 是可区分的,所以 A,G 输入 1 到达了不同状态,因此 A,G 也是可区分的。同理 E,G 也是可区分的:

image-20210615233306765

此时剩下的都是不可区分的状态对。

4.4.2 DFA 最小化

将等价的状态合并,即可完成最小化。