有穷自动机 本章介绍有关有穷自动机的基本概念和 理论以及正规文法、正规表达式与有穷 自动机之间的相互关系。

Presentation on theme: "有穷自动机 本章介绍有关有穷自动机的基本概念和 理论以及正规文法、正规表达式与有穷 自动机之间的相互关系。"— Presentation transcript:

1 有穷自动机 本章介绍有关有穷自动机的基本概念和 理论以及正规文法、正规表达式与有穷 自动机之间的相互关系。

2 有穷自动机（FA） 确定有穷自动机（DFSA） 非确定有穷自动机（NDFSA） 确定与非确定有穷自动机的等价和转换
右线性文法与有穷自动机的等价和转换 正规表达式与有穷自动机的转换

3 3.1 有穷自动机的形式定义 输入一个字符串，判断其是否是合法的 C 语言标 识符；
输入一个字符串，判断其是否是 形式(即先 输入a、再输入b、最后输入c，且输入的a、b、c的 个数相同）； 针对类似的字符串识别问题，建立有限状态自动 机模型，可以为分析、求解带来很大的帮助。 自动机是一种能进行运算并能实现自我控制的装置。它是描述符号串处理的强有力的工具，因而成为研究词法分析器的重要基础。

4 有限状态系统的概念 状态：可以将事物区分开的一种标识。 具有离散状态的系统：如数字电路(0,1)，十字路口 的红绿灯等。系统中状态是离散的。
具有连续状态的系统：比如水库的水位，室内温 度等。系统中状态可以连续变化，即有无穷个状 态。 有限状态系统必然是离散状态系统，而且只有有 限个状态。 有穷自动机就是这种有限离散状态系统的抽象数学模型。在这种模型中，系统在一些离散的带上从一个状态移动到另一个状态；每一次转换都是由当前的状态及一组输入符号确定；在这种转换中，它也可以输出某些离散的值集。

5 例1：打电话（自动机在通信领域的应用） 在一次呼叫中，从建立连接到通话完毕，要经历摘机、拨号、应答、进行通话等过程，可以分别用五个状态来表示。 Example 1 q0: 空闲状态 q1: 等待拨号音状态 q2: 可以拨号状态 q3: 等待应答状态 q4: 通话状态

6 以上例子可以抽象为FA 具有离散输入输出（可以没有输出，比较特殊的 也可以没有输入）； 有限的状态； 对象处于某一相对稳定的状态下；
某个事件（输入）发生； 这一事件引起一串处理发生，包括执行特定的功 能，产生相应的输出等； 处理结束，迁移到一个新的相对稳定的状态。

7 FA的模型 FA可以理解成一个控制器，它读一条输入带上的字符。 控制器包括有限状态 从左到右依次读取字符
状态 + 激励 ——〉状态迁移（根据当前所处状态和输入字 符进行转移） 每次状态迁移的后继状态唯一，则是确定有穷自动机 每次状态迁移的后继状态不唯一，则是非确定有穷自动机 一个有限控制器 一个读头 一条写有字符的输入带

8 确定有穷自动机（DFA） 的形式定义 定义: DFA是一个五元组 DFA=(Q,∑,t,q0,F)
∑ : 有穷输入字母集，它的每个元素称为一个输入符号 t: 单值映射转换函数集合: Q× ∑  Q。 t(q,a)=q’ 意指：现行状态为q,面临输入字符a时，将转到下一状态q’ ， q’ 称为q的一个后继状态。 q0: 初始状态， q0  Q F: 终止状态集, F  Q 表示方式: 状态转换图 状态转换表

9 3.1.1 状态转换图 一个DFA,能识别由带符号或无符号十进制数组成的语言。如果扫描完输入串，在一个停止状态上结束，则称这个串被接收了，否则不被接收。它接收如下的串： ;不接收 等 Example 3 Q = {S,A,B,G,H} ∑ = {+,-,d,.} t(S,+)=A t(S,-)=A t(S,.)=G t(S,d)=B t(A,d)=B t(A,.)=G t(B,d)=B t(B,.)=H t(G,d)=H t(H,d)=H q0 = S F = {B,H} 状态转移图

10 . - 3.1.2 状态转换表 d 输入符号 S + A G B *B *H H 状态 状态转换函数之值 ∑ = {+,-,d,.}
Q = {S,A,B,G,H} ∑ = {+,-,d,.} t(S,+)=A t(S,-)=A t(S,.)=G t(S,d)=B t(A,d)=B t(A,.)=G t(B,d)=B t(B,.)=H t(G,d)=H t(H,d)=H q0 = S F = {B,H} 状态 状态转换函数之值

11 DFA的映射扩充 为了讨论自动机的等价性，先对DFA中的映射进 行扩充。
定义3.2 DFA=(Q,∑,t,q0,F)，扩充的映射t:Q× ∑*  Q，定义为 t(q, ε) = q t(q, a) = t(t(q,a),) 其中，q  Q，a∑, ∑* 。 定义3.3 DFA=(Q,∑,t,q0,F)，如果t(q0，)=qF, 则称符号串可被该有穷自动机DFA所接受。 P29，例3.4

12 3.1.3 自动机的等价性 由有穷自动机A接受的符号串集，记为L(A)。
定义3.4 两个有穷自动机A1和A2，如果L(A1)=L(A2)， 则称自动机A1和A2等价。 A1和A2是等价的，当且仅当对每一个串x， A1接 收x当且仅当A2接收x。 P30，例3.5

13 3.1.4 NDFA 的形式定义 定义: NDFA是一个五元组 M=(Q, ∑,t,Q0,F) Q: 非空有穷状态集
∑ : 非空有穷输入字母集 t:是Q× ∑  Q的子集，即t是一个多值映射 Q0: 初始状态， Q0  Q F: 终止状态集, F  Q

14 NDFA的映射扩充 定义3.6 NDFA=(Q,∑,t,q0,F)，扩充的映射t:Q× ∑*  Q的子集，定义如下：
t(q, a) = t(q1, )U t(q2, )…… U t(qn, ) 其中，a∑, ∑+ , t(q, a) ={q1，q2……，qn} 定义3.7 NDFA=(Q,∑,t,q0,F)，对于一个符号串 ∑*，如果q t(q0, ), q0Q，而qF，则称符号 串可被该非确定有穷自动机所接受。 P30，例3.7

15 一个NDFA x y 1 2,3 1 * 2 1 2,3 3 4 4 4 2,4 4 对于NDFA来说，所谓的识别符号串是指：对于∑+中的任何串,若存在一条从某一初始结点到一终止结点路径，且这条路径上所有弧的标记依次连接的串等于,则称可以为该NDFA所识别或接收。如果某些状态既是初态又是终态，或者存在一条从某个初态到某个终态的ε路径，则空串ε可以被识别或接收。 Example 4

16 DFA 和 NDFA 的主要区别 NDFA 有一个开始状态集，而 DFA 只有一个开始状 态
NDFA 的映射是Q× ∑  Q的子集，是一个多值 映射， 而 DFA 的映射是Q× ∑  Q，是一个单 值映射 εNDFA 在没有扫描任何符号的情况下，也可以进行 移动，而这种移动称为空移。我们用表示法 t(q, ε) = {某些状态的集合} 将空移情况包含在状态转换函数中。按这种方式 ，从一个非终结状态经由一个或多个空移可以到 达某个终止状态。

17 3.2 NDFA到DFA的转换 通过下述步骤可将一个NDFA转换称等价的DFA： ① 寻找并消除空移环路； ② 消除余下的空移；
①  寻找并消除空移环路； ② 消除余下的空移； ③ 确定化。

18 3.2.1 空移环路的寻找和消除 例 图(a)所示的是一个NDFA，结点q0是开始状态，q3是终止 状态，结点q0、q1与q4形成一个空移环路。要消除这个空移 环路，只需将3个结点q0、q1与q4合并成一个结点，以q0标记 ，并消除原来3个结点之间所有的环。由于这3个结点中的q0 是开始状态，因此，合并之后的新结点q0被设置为开始状态 ，如图(b)所示。 图 3.4 消除空移环路

19 3.2.2 消除空移 下面给出一个消除空移的算法： 给定从状态A到B的一个空移(即从状态A到B经由连线的一个 转换，换言之，t(A,)={…，B，…})。置t(A,)=，对每 个a和q，如果qt(B,a)，则将q加到t(A,a)。如果A是开始状 态，则将B也加入开始状态集。如果B是终止状态，则将A也 加入终止状态集。 图3.6 消除空移 图3.5 空移

20 3.2.3 确定化——子集法 设NDFA M=(Q, , t, Q0, F)是一个非确定有穷自动机，它的语言（即它能接受的符号串集合）记为L(A)。那么，一定可以构造一个和它等价的确定有穷自动机DFA M=(Q, , t, q0, F)，使L(A)=L(A)。构造如下： A的输入字母表和A的输入字母表完全相同。 把A的每一个状态子集都作为A的一个状态。因此，此构造方法称为子集法。 设A的任一状态子集{r1, r2,…, rn}, riQ(i=1,2,…n)。令r=[r1, r2,…, rn],rQ。取a, A的映射定义t(r,a)= qQ。其中q=[q1, q2,…, qm],而 {q1, q2,…, qm} = t(r1,a)∪t(r2,a)∪…∪t(rn,a)。 若S={S1, S2,…, Sj }是A的初态，则S=[S1, S2,…, Sj]是A的初态。 若p是A的一个终态，则A中每一个包含p的状态[…，p，…]都是A的一个终态。

21 P42，例3.10 例3.6中的NDFA状态转化图

22 3.2.4 确定化——造表法 表3.2 造表法确定化 输入 状态 X y [q0] q0’ q1’ q2’ q3’ q4’ q5’
表3.2 造表法确定化 输入 状态 X y [q0] q0’ q1’ q2’ q3’ q4’ q5’ [q1 , q2] [q0] [q1 , q2] [q0 , q3] [q1 , q2 , q3] [q0 , q3] [q0 , q3] [q1 , q2 , q3] [q1 , q2 , q3] [q0 , q1 , q3] [q1 , q2 , q3] [q0 , q1 , q3] [q0 , q1 , q2 , q3] [q0 , q1 , q2 , q3] [q0 , q1 , q2 , q3] [q0 , q1 , q2 , q3] [q0 , q1 , q2 , q3]

23 6 1 a  2 3 4 5 7 8 设I={1} 则 -closure(I)={1，2} J={5，4，3}
Ia= -closure(J)= -closure({5，4，3}) ={5，4，3，6，2，7，8}

24 造表法的具体步骤 假定给定的NDFSA M中仅含两个符号a，b。可用如下方 法将M确定化：采用造表的方式，该表的每一行有三列(若 中含有n个符号，则该表有n+1列)，第一列记为I，第二 、三列分别记为Ia ,Ib 。 ① 置该表的第一行第一列为-closure(Q0)，即一列包含 M初态集Q0 的ε-闭包。然后计算它的Ia 和Ib,分别填入第 二、三列上，一般，若某一行的第一列上的I已确定，便 可根据前述定义求出这一行的第二、第三列上的Ia 和Ib 。 ② 检查Ia 和Ib，看它们是否已在表的第一列中出现，把 未曾出现者之一填入下一空行的第一列上，再计算该行的 第二、第三列上的Ia 和Ib。

25 ③ 重复第二步，直至表中所有第二、第三列上的元素全 部再第一列出现为止。
因为M中的状态(子集)的个数是有限的，所以上述三步必 定在有限步内终止。 ④ 将由上述过程得到的最终形式的表看作一个状态转换 表，即把其中第一列中的元素作为状态，把Ia ,Ib分别看 作是输入符号a，b，把其余信息看作是状态转换函数之值 。这个表唯一地刻画了一个确定的有穷状态自动机M，其 初态是该表第一行第一列的元素，其终态是该表中所有那 些含有原终态的元素。可以证明，这个DFSA M和NDFSA M 是等价的。

26 X Y  5 1 4 2 3 6 a b I Ia Ib {X,5,1} {5,3,1} {5,4,1} {5,3,1} {5,2,3,1,6,Y} {5,4,1} {5,4,1} {5,3,1} {5,2,4,1,6,Y} {5,2,3,1,6,Y} {5,2,3,1,6,Y} {5,4,6,1,Y} {5,2,4,1,6,Y} {5,3,6,1,Y} {5,2,4,1,6,Y} {5,2,3,1,6,Y} {5,4,6,1,Y} {5,3,6,1,Y} {5,3,6,1,Y} {5,2,4,1,6,Y} {5,4,6,1,Y}

27 确定化的状态转换表 I a b 1 2 3 4 6 5 确定化的状态转换图 1 2 3 5 4 6 a b

28 3.2.6 消除不可达状态 在自动机中，从开始状态没有任何一条路径能达到的状态称为不可达状态。由于不可达状态事实上是无用的，因此可以删除它们。下面给出识别可达状态的算法。当该算法终止时，每一个未标记的状态就是不可达状态。 识别DFA中可达状态的算法。 ①标记开始状态S； ②给定任意标记过的状态P，如果对某个输入符号存在从状态P到Q的转换，则标记每一个这样的状态Q； 重复步骤②，直到不再有可标记的状态为止。

29 图3.11 DFA的状态转换图

30 3.2.7 DFA的简化 所谓确定有穷自动机M的化简是指：寻找一个状态 数比M少的确定的有穷自动机M，使得L(M)= L(M) 。
定义3.10 假定q1和q2是M中的两个不同状态，称q1 和q2是等价的：如果从状态q1出发能扫描任意串w 而停止于终态，那么从状态q2出发也能扫描同一个 串w而停止于终态；反之，亦然。 定义3.11 如果两个状态q1和q2不等价，则称这两 个状态是可区分的。

31 3.2.8 对DFA化简的基本思想 将状态集分解成若干个互不相交的子集，使每个 子集中的状态都是等价的，而不同子集的状态则 是不等价的，即是可区分的。 由于终止状态与非终止状态是可区分的，所以先 将状态集分解成两个子集，终止状态集和非终止 状态集； 然后对每个子集进行再分解，分解后的两个状态 属于同一个子集，当且仅当对于任何一个输入字 母，它们的映像属于同一个子集。 此过程一直执行到不能分解为止。

32 先将所有终止状态归为一个子集S1={q1’, q3’, q4’, q5’}，其余的非终止状态子集S2={q0’, q2’}。
因为t(q1’,x)=q2’S2，而t(q3’,x)=q4’S1 ，t(q4’,x)=q5’S1 ，t(q5’,x)=q5’S1 。所以将S1分解成两个子集S1’={q1’}， S2’={ q3’, q4’, q5’} 又因为t(q0’,x)=q1’ S1’ ，t(q2’,x)=q3’ S2’，所以将S2分解成两个子集{q0’}和{q2’} 以q3’作为S2’的代表，便可得化简后的DFA.

33 从化简后的DFA到程序表示 识别标识符的DFA1（见图 (a)）需改为图 (b)所示状态，其 中，l代表字母，d代表数字。
如果赋予状态q0、q1与q2一定的操作，则可得识别单词标识 符的程序流程图(见下图)。

34 我们也可以直接用程序代码来表示一个自动机。
State: = 0 While (c=getchar()≠””) do Begin case state of 0: if(c >= ‘0’and c<=‘9’)then state:=2 else if(c=‘+’ or c=‘-’)then state:=1 else if(c=‘.’) then state:=3 else ERROR(); break; 1: if(c >= ‘0’and c<=‘9’)then state:=2 2: if(c >= ‘0’and c<=‘9’)then state:=2 else if(c=‘.’) then state:=4 3: if(c >= ‘0’and c<=‘9’)then state:=4 4: if(c >= ‘0’and c<=‘9’)then state:=4 else ERROR(); end end;

35 3.3 正规文法与有穷自动机 正规文法与有穷自动机FA有着特殊的关系。
3.3 正规文法与有穷自动机 正规文法与有穷自动机FA有着特殊的关系。 可以证明：对任何正规文法G，可以构造一个FA， 它能而且只能识别语言L(G);反过来，对任何FA， 可以构造一个相应的正规文法G，它能生成由该FA 所识别的语言。

36 3.3.1 从正规文法到FA 设正规文法G有形如U→aV(aVT, VVN或V=)的产生式。由正规文法G可以直接构造一个有穷自动机A(简称自动机A)，使L(A)=L(G)。构造步骤如下： ① 令正规文法G的终结符号集作为有穷自动机A的字母表； ② 文法G的每一个非终结符都作为自动机A的一个状态，特别是文法G的开始符作为自动机A的开始状态； ③ 在自动机A中增加一个新状态z作为自动机的终止状态； ④ 对于文法G的形如U→aV(aVT或a=,VVN)的产生式，在自动机A中构造形如t(U, a)=V的映射； ⑤ 对于文法G的形如U→a(aVT)的产生式，在自动机A中构造形如t(U,a)=z的映射。

37 设正规文法G19[S]: S →aS|aA|bB A →bA|cC B →aB|dD C →cC|c D →dD|d
Example 3.14

38 3.3.2 从FA到正规文法 从正规文法可直接构造其自动机，反之，由自动机也可直接构造其正规文法。构造步骤如下：
① 自动机每一个状态的标记，均作为正规文法的非终结符，其中，自动机开始状态的标记将作为正规文法的开始符号。自动机的输入字母表中的所有符号，作为正规文法的终结符。 ② 对于自动机的映射t(U, a)=V（其中，U、V为自动机的状态标记；a为输入符号），构造文法的一条产生式 U→aV U、V为文法的非终结符，a为终结符。 ③ 对于自动机的终止状态Z，在正规文法中增加一条产生式 Z→ P39，例3.15

39 3.4 正规表达式与FA 正规表达式的定义 正规表达式与FA的对应性 正规表达式到NDFA的转换 NDFA到正规表达式的转换
从正规文法到正规表达式

40 3.4.1 正规表达式的定义 正规表达式是用于描述称之为正规集的语言类 的一种表示形式。
正规表达式的定义 正规表达式是用于描述称之为正规集的语言类 的一种表示形式。 定义3.12 字母表上的正规表达式和正规集递归定义如下： ① a，a是上的一个正规表达式，它所表示的正规集为{a}。 ② 空串是上的一个正规表达式，它所表示的正规集为{}。 ③ 空集是上的一个正规表达式，它所表示的正规集为。

41 ④ 设e1与e2都是上的正规表达式，它们所表示的正规集分别为L(e1)与L(e2)，则
i) e1e2也是正规表达式，它所表示的正规集为 L(e1e2)=L(e1)∪L(e2)； ii) e1 e2也是正规表达式，它所表示的正规集为 L(e1 e2)=L(e1)L(e2)； iii) (e1)*也是正规表达式，它所表示的正规表达式为 L((e1)*)=(L(e1))*。 这3个运算符的优先顺序为：‘*’优先，‘.’次之，最后是‘|’。

42 设={a,b},在其上定义的部分正规表达式和相应的正规集如下： 正规表达式 正规集 a {a} b {b} ab {ab}
正规表达式 正规集 a {a} b {b} ab {ab} a|b {a,b} a* {a}*={,a,aa,aaa,…} ba* {b}{a}*={b,ba,baa,…} Example 3.16

43 定义3.13 设e1与e2是上的两个正规表达式，若 L(e1)=L(e2)，则称e1与e2等价，记为e1=e2，如
a(ba)*=(ba)*a 定理3.1 设e1、e2和e3都是上的正规表达式，则 ① e1e2= e2e1 (交换律) ② (e1 e2) e3=e1(e2 e3), (e1e2)e3= e1(e2e3) （结合律） ③ e1(e2e3)= e1 e2e1 e3, (e1e2) e3= e1 e3 e2 e3 （分配律） ④  e1= e1= e1

44 3.4.2 正规表达式与FA的对应性 正规表达式和FA是定义语言（符号串集）的两 种不同形式。同一个语言，既可用FA描述，也 可用正规表达式描述。而且，两者之间可以互 相转换。

45 3.4.3 正规表达式到NDFA的转换 对于字母表上任意一个正规表达式e，一定可 以构造一个NDFA M，使L(M)=L(e)。方法如下：
先构造一个NDFA M的一个广义转换图，其中，只有S 与Z两个状态，S是开始状态，Z是终止状态，弧上是 正规表达式e。 然后，按照下图所示的替换规则对正规表达式e逐步 进行分解，直到转换图中所有的弧上都是中的单个 符号或为止。

46 替换规则1 （1） 替换成 （2） 替换成 （3） 替换成

47 S Z (a|b)*(aa|bb)(a|b)*  5 1 4 2 3 6 a b
图3.19 构造正规表达式的NDFA

48 3.4.4 NDFA到正规表达式的转换 对于一个具有输入字母表的NDFA M，在上也可 以构造一个正规表达式e，使L(e)=L(M)。具体操 作如下： 首先，对NDFA M进行拓广，在M的状态转换图中，新设置 一个唯一的开始状态S和唯一的终止状态Z，并允许状态 转换图中弧上可以为正规表达式。 然后，从开始状态S到原来所有的开始状态连接弧，再 从原来所有的终止状态到Z状态也连接弧。修改后,构成 了一个新的NDFA，它只有一个初态结点S和一个终态结点 Z，这个新的NDFA M′显然和原NDFA M等价。 接着，利用下图所示的替换规则，逐步消去M′中属于M 的所有结点和有关连线，直到状态转换图中只剩下状态S 和Z为止(这个过程称为消结)。在消结过程中，用相应的 正规表达式标记连线。

49 替换规则2（P43，例3.18） （1） 替换为 （2） 替换为 （3） 替换为

50 3.4.5 从正规文法到正规表达式 从正规文法到正规表达式的转换规则如下：
从正规文法到正规表达式 从正规文法到正规表达式的转换规则如下： ① 产生式U→V,V→,VVN，, VT*，转换成 正规表达式U=； ② 产生式U→U，转换成U=*； ③ 产生式U→，转换成U=。 正规文法G21[S]： S →dA|eB A →aA|b B →bB|c 根据规则，可将产生式A →aA|b转化为A=a*b;将B →bB|c转化为B=b*c;则有产生式S →da*b|eb*c，转化为S=da*b|eb*c。 所以，正规文法G的等价正规表达式是da*b|eb*c Example 3.19

51 3.5 DFA在计算机中的表示 对于一个DFA=(Q, , t, q0, F)，如果给出了它 的映射t：QQ，那么，这个DFA实际上也就确 定了。因此，要在计算机中表示一个DFA，只需在 计算机中表示它的映射。 矩阵表示法 表结构

52 3.5.1 矩阵表示法 DFA的映射t:QQ，可表示成t(q,a)=q，其中，q ，qQ，a。
映射t(q,a)=q，在计算机中自然可用矩阵来表示， 其中，状态q作为矩阵的行，输入字母a作为矩阵的 列，映象q作为矩阵元素t(q,a)的值。 将状态集Q中的所有状态排一个序：q0,q1,q2,…,qn ；输入字母表中的所有字母也排一个序： a1,a2,…,am。 设M是一个二维数组,若t(qi,qj)=qk，则令M[i,j]=k ，其中，i，k=0,1,2,…,n；j=1,2,…,m。 P44,例3.20

53 3.5.2 表结构 DFA的映射t:QQ，在计算机中可表示成一种表 结构。在这个表结构中，每一个状态对应一个表 ，表中包括该状态的状态名、从该状态发出的弧 数、每条弧上的标记（输入字母）以及弧达到的 状态所在表的首地址。 P44,例3.21

54 The end