ITOC chapter1 正则语言

Chapter 1: Regular Languages 正则语言

计算理论的第一个问题:什么是计算机?

现实的计算机很复杂,所以我们采用叫做“计算模型“的理想计算机。

最简单的模型:有穷自动机

1.1 Finite Automata 有穷自动机

DFA Deterministic Finite Automaton
NFA Nondeterministic Finite Automata

Definition定义:

确定型有穷自动机DFA是一个五元组(Q,Σ,δ,q0,F), 其中

  1. Q 是一个有穷集合,叫状态集。
  2. Σ 是一个有穷集合,叫字母表。
  3. δ:Q×ΣQ 是转移函数。
  4. q0Q 是起始状态。
  5. FQ 是接受状态集。

DFA可以没有接受状态(接受状态集为空)

若集合A是有穷自动机M接受的全部字符串集,那么A是M的语言,L(M)=A,M识别语言A

计算的形式定义:

设 N=(Q,Σ,δ,q0,F) 是一台NFA,w=y1y2..yn是字母表 Σ上的一个字符串。如果存在Q中的状态序列r0,r1,,rm满足:

  1. r0=q0
  2. ri+1δ(ri,yi+1), (i = 0,…,m – 1,)
  3. rmF.

那么N接受w。

正则语言

如果一个语言被一台有穷自动机识别,那就属于正则语言。

正则运算

正则运算的定义如下:
假设A和B都是正则语言:

  • 并: AB={x|xA or xB}.
  • 交: AB={x|xA and xB}.
  • 连结: AB={xy|xA and yB}.
  • 星运算: A={x1x2xk|k0 and each xiA}.只作用于一个语言,一元运算
    (不管A是啥,空串总是A∗的一个元素)

定理:正则语言在并运算下封闭

简单说就是,如果A和B都是正则语言,那么AB也是正则语言。

证明方法:构造 M 识别 A∪B

通过笛卡儿积模拟同时跑 A和 B 的 DFA,若其中一个 DFA accepts 则 M accepts。

定理:正则语言在连结运算下封闭

要构造 M 识别 A∘B,即输入可以分成两段,M1接受第一段且M2接受第二段。但M不知道应该在哪断开两段。

于是引入NFA (Nondeterministic Finite Automaton)

1.2 Nondeterminism 非确定性

DFA中,给定状态和下一个读入字符,下一个状态是确定的,NFA中,下一个状态可以有多个选择

定义:

非确定型有穷自动机是一个五元组(Q,Σ,δ,q0,F), 其中:

  1. Q 是一个有穷集合,叫状态集。
  2. Σ 是一个有穷集合,叫字母表。
  3. δ:Q×Σ⟶P(Q) 是转移函数。
  4. q0Q 是起始状态。
  5. FQ 是接受状态集。
计算的形式定义:

设 N=(Q,Σ,δ,q0,F) 是一台NFA,w是字母表 Σ上的一个字符串。如果能把w写成w=y1y2..yn,每一个yi都是Σε的一个成员,并且存在Q中的状态序列r0,r1,,rm满足:

  1. r0=q0
  2. ri+1δ(ri,yi+1), (i = 0,…,m – 1,)
  3. rmF.

那么N接受w。

NFA与DFA的等价性

形式上看起来,NFA可以有多种状态,感觉比DFA的能力强,但实际上他们的能力是等价的。

这出乎意料,但很有用。因为描述给定语言的NFA有时比DFA容易得多!

定理:每一台非确定型有穷自动机都有一台等价的确定型有穷自动机。

证明方法:任意一门语言能被NFA识别,证明也一定存在一台DFA也识别这门语言,把NFA转化为模拟它的DFA。

个人理解:把 NFA 里的当前的多个状态组合成一个集合,那么状态转移就是从一个集合转移成另一个集合,一对一,就是 DFA。

推论:一个语言是正则的,当且仅当有一台NFA识别它。

定理:正则语言在连结运算下封闭

简单说就是,如果A和B都是正则语言,那么AB也是正则语言。A–M1 B–M2

证明方法:构造NFA M 识别 M1∘M2,即输入可以分成两段,M1接受第一段且M2接受第二段。只要M1进入接受状态,就让M的非确定性分支进入M2。

1.3 Regular Expressions 正则表达式

运算符优先顺序:*>∘>∪  先做星运算,再做连结运算,再做并运算。

定义:

如果R是:

  1. a, a是字母表Σ中的一个元素,
  2. ε,
  3. ∅,
  4. (R1∪R2), R1和R2都是正则表达式,
  5. (R1∘R2),R1和R2都是正则表达式,
  6. (R1∗),R1是正则表达式.

那么R是一个正则表达式。

ε表示只包含一个字符串ε的语言,而∅表示不包含任何字符串的语言。

正则语言与DFA/NFA的等价性

是正则语言  能被正则表达式描述

前面提到“一个语言是正则的,当且仅当有一台NFA识别它”,所以:

能被 DFA/NFA 识别  能被正则表达式描述

具体证明:

能被正则表达式描述  是正则语言

正则表达式定义的前三点显然是正则语言,因为正则语言在正则操作下封闭(后三点),加上正则表达式是递归定义,所以能被正则表达式描述  是正则语言。

能被 DFA/NFA 识别  能被正则表达式描述:

引入 GNFA (Generalized Nondeterministic Finite Automaton):

GNFA 在 NFA 的基础上额外多了三点要求:

  1. 开始状态不能为接受状态,且入度为 0,作为“起点”
  2. 只有一个接受状态,且其出度为 0,作为“终点”
  3. 除了以上两个状态,任意一个状态都有箭头到达任意一个状态(包括自身)

把DFA转化为GNFA:

  1. 添加一个新的起始状态和一个新的接受状态,新接受状态到原接受状态加一个ε箭头
  2. 每一个原接受状态都往新接受状态添加一个ε箭头(重复则合并)
  3. 两两没有箭头的状态,加上∅箭头。完成!

把 GNFA 转化成正则表达式:

  1. 把任意一条从开始状态(起点)到接受状态(终点)之间的路径上的串(即被接受的串)并成一个正则表达式(删除一个状态)
  2. 递归地重复第一点的操作直至剩下两个状态(起点和终点)。

当最终只剩下起点和终点时,就只剩下了一个箭头,其上的 label 就是与其等价的正则表达式。

过程CONVERT(G),输入一台GNFA,输出等价的正则表达式:

  1. 设k是G的状态数
  2. 如果k=2,输出R
  3. 如果k>2, 任取一个状态 qripQ{qstart,qaccept}
    令G′为GNFA(Q,Σ,δ,qstart,qaccept) , 这里Q=Q{qrip},
    并且对于每一个 qiQ{qaccept} 和每一个 qjQ{qstart}, 令
    ε(qi,qj)=(R1)(R2)(R3)∪(R4),
    其中R1=δ(qi,qrip)R2=δ(qrip,qrip)R3=δ(qrip,qj),  R4=δ(qi,qj).
  4. 计算 CONVERT(G’) (递归调用自身)

断言:对于任意GNFA,CONVERT(G)等价于G。(可使用归纳法证明)

1.4 Nonregular Languages 非正则语言

B={0^n1^n|n0}需要记录读多少个零,0个数可以无穷个,有穷自动机有限状态无法记住无数个0。–非正则语言

C={w|w中0和1的个数相等}–非正则语言

D={w|w中01和10作为子串出现的个数相等}–居然是正则语言!

Pumping Lemma 泵引理

设A是一个正则语言,那么存在一个数p(the pumping length) 使得:如果s是A中任一长度不小于p的字符串,那么s可以被分成三段s = xyz,满足:

  1. for each i0,x(y^i)zA,
  2. |y|0, and
  3. |xy|p.

证明方法:

  1. 令 p 为 DFA 的状态数
  2. 当 DFA 接受一个长度至少为 p 的串时,根据鸽巢原理,至少存在一个状态重复出现,即出现环
  3. 令环之前的串为 x,环上的串为 y,环后的串为 z
  4. 我们可以绕这个环y重复走任意圈,再到达接受状态,故x(y^i)z 同样会被该 DFA 接受

B={0^n1^n|n0}

根据Pumping Lemma分成三段xyz:

  1. y只包含0:字符串xyyz的0比1多,不属于B,违反条件1.
  2. y只包含1:同上
  3. y包含0和1:xyyz中0和1的个数可能相同(x于z长度不同就不同)但是这样在xyyz中第二y的0前面出现了1,也不属于B,矛盾。

因此,B不是正则的。

C={w|w中0和1的个数相等}

取s=0^p1^p,满足C,根据Pumping Lemma s=xyz,如果令x=z=空,y=0^p1^p好像可以,但根据条件3,|xy|p,那么y一定只能全都是0,xyyz就不属于C,给出矛盾,因此C不是正则的。

D={w|w中01和10作为子串出现的个数相等}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注