第二章 形式语言与自动机理论基础(有限自动机)

1、2.2 有限自动机 (Deterministic Finite Automata) 一 . DFA的定义 二. DFA的三种表示 三. DFA接受的语言 2.2.1 确定的有限自动机(DFA) 一 DFA M定义 一个确定的有限自动机 DFA M是一个五元组 （，S，S0，Z，f） 是一个字母表，它的每个元素称为一个输入符号。 S是一个有限状态集合。 S0S，S0 称为初始状态。 Z是S的子集，称为终结状态集合。 f是一个从S 到S的单值映射 f(，)（,S，） 表示当前状态为q,输入符号为a时，自动机将转换到下一 个状态，称为的后继。 例 设（， ，f）其中 f（，），f（，） f（，），f

2、（，） f（，），f（，） f（，），f（，） 二 的三种表示： （1）用转换函数 （2）转移矩阵 （3）状态转换图 所谓确定的状 态机，其确定 性表现在状态 转移函数是单 值函数！ （1）用转换函数 f（，），f（，） f（，），f（，） f（，），f（，） f（，），f（，） （2）转移矩阵 ab 012 132 213 333 横坐标 纵 坐 标 0 1 3 2 a a a a bb b b 3 （3）状态转换图 结点表示状态，箭弧标记为字母表中的字母 输入 字符 状态 a b 0 1 2 1 3 2 2 1 3 3 3 3 终结状态如何表示？ 三 DFA M 接受的语言(字符串集) 如

3、果对所有*，以下述方式递归地扩充f的定义 f（，） f(，）f(f(，w），） 对于上例中的DFA M 和 w=baa， f(0，baa）=f(2,aa）= f(1, a）=3 0 1 3 2 a a a a bb b b 3 0 b 2 a 1 a 3 3 该DFA M能够识别字符串baa 从状态转换图看，从初态出发，沿任一条路径到达终结 状态，这条路径上的弧上的标记符号连接起来构成的符号 串为DFA M 所识别。 DFA M 所能识别的符号串的全体记为L(M)，称为DFA M所识别的语言。 （）*，若存在Z， 使f（，） 2.2.2 非确定的有限自动机（NFA） Nondeterminis

4、tic Finite Automata 一. NFA m的定义 二. FA 的等价定理 三. 具有-转移的NFA构造DFA的算法 非确定有限自动机M是一个五元组 M（，S，S，Z，f） 其中，S，Z的意义和DFA的定义一样，其中S表示 初始状态集，f是一个从S()到S的子集的映射，即f： S() S，其中S是S的幂集，即S中所有子集组 成的集合。 一 NFA的形式定义: 确定的和非确定的有限自动机之间的重要区别是 1、状态转换函数是一个多值映射；反映在状态转换图 上即对同一弧标记到达的状态结点不惟一。 2、NFA初态集，而DFA是一个唯一的状态. NFA存在 弧标记 0 1 3 2 a b a

5、 bb a b 3 类似FA，NFA m可用状态转换图表示， 如果f(， ）=1，2 . . . ，k ，则从q出发分别向1， 2 . . . ，k各画出一条标记为a的箭弧(非确定的含义)。 同理可定义NFA m所识别（接受）的语言。 *中所有 可能被NFA m所识别的符号串的集合记为L(M)。 NFA M所识别的语言为: L(M)=|f(q 0,)=q q Z 定理 对任何一个NFA M，都存在一个 DFA M，使L(M)=L(M) 构造方法：用M的一个状态对应M的多个状态，用这种 方法，能从一个NFA M构造一个等价的DFA M，称作子集 构造法。 二. FA 的等价定理 NFA M=(S

6、,NFA M=(S, ,f,S,f,S0 0,Z),Z) 等价的等价的DFA M=(S,DFA M=(S, ,f,S,f,S0 0,Z),Z) 1)S=2S (由NFA M的状态集S的所有子集组成) 2)Z=K|K S且K Z （Z是由至少包含Z中一个状态S的 所有子集组成） 3)3)S S0 0=S=S0 0 4)4) = = 5)5)f(K,a)=P, f(K,a)=P, 其中其中K,PK,PS 且 P=p|pf(q,a),qk 6)DFA M 的f: f(k1,k2,ki,a)=p1,p2,pi 当且仅当 7)NFA M 的f: f(k1,k2,ki,a)=p1,p2,pi 证明 （略P

7、30） 定义 集合I的-闭包： 令I是一个状态集的子集，定义-closure（I）为： 1）若sI，则s-closure（I）； 2）若sI，则从s出发经过任意条弧能够到达的 任何状态都属于-closure（I）。 状态集-closure（I）称为I的-闭包 通过例子来说明状态子集的-闭包的构造方法 三、具有-转移的NFA构造等价DFA的方法 例： 如图所示的状态转换图： 令I=1， 求-closure（I）=？ 1 5 6 4 3 2 a a 根据定义： -closure（I）=1，3，5 构造等价DFA算法 若t1是NFA的初态，DFA的初态A= closure(t1 )。 对NFA中每一

8、个箭弧标记m，计算closure(f(q,m)，其中q为 已生成的DFA状态。遍历字母表的每个字符为输入 例如字母表为a,b B= closure(f(A,a) C= closure(f(A,b) 如果B和C不为空集，重复这一过程，直到不在出现新的状 态集合） D= closure(f(B,a) E= closure(f(B,b) F= closure(f(C,a) G= closure(f(C,b) 注意: D,E,F,G中相等的集合合并,空集则舍去. closure (f(A， a)的含义 NFA中从集合A中的状态出发，先经若干 箭弧，接着经标记为a的箭弧到达的状态 集合的closure

9、。 01 4 23 6 5 789 10 a a b bb 01 2 4 A=0,1,2,4,7 a 3 a 8 6 1 2 4 7 B=3,8,6,1,2,4,7 a C=5,1,2,4,6,7 从NFA出发构造DFA b 7 b 5 6 71 2 4 a b a b statesab B=3,8,6,1,2,4,7 A=0,1,2,4,7B C=5,6,1,2,4,7 C B D=5,9,6,1,2,4,7 D BC B E=5,10,6,1,2,4,7 E BC 等价DFA的转移矩阵 等价的DFA的状态转换图 ABD startabb C b b b a a a a E 注意：包含原初始

10、状态0的状态子集A为DFA M的初态 包含原终止状态10的状态子集E为DFA M的终态。 例：有NFA M A =-closure(1)=1,4a 1 2 3 4 start a b a c c B =-closure(f(A,a) ) =-closure(f(1, 4 ,a) =-closure(f(1,a)f(4,a) = -closure(2,3） = -closure (2,3) =2,3 C =-closure(f(A,b) ) = -closure(f(1,b)f(4,b) = -closure(） = D =-closure(f(A,c) ) = -closure(f(1,c)f

11、(4,c) = E =-closure(f(B,a) ) F =-closure(f(B,b) ) G =-closure(f(B,c) ) B =-closure(f(A,a) ) C =-closure(f(A,b) ) D =-closure(f(A,c) ) DFA M的状态图： A B D C E start 1,4 2,3 4 2 ac a b b c 注意：包含原初始状态1的状态子集为DFA M的初态 包含原终止状态4的状态子集为DFA M的终态。 3,4 具有-转移的NFA构造等价DFA的方法 不具有-转移的NFA如何构造等价DFA？ 例 NFA M=(0,1 , q0,q1,

12、q0, q1, f),其中 f(q0 ,0)= q0,q1, f(q0,1)= q1 f(q1,0)= f(q1,1)= q0,q1 q0q0q1 0 0 1 1 1 start q0q0q1 0 0 1 1 1 start f(q0 ,0)= q0,q1, f(q0 ,1)= q1 f(q1 ,0)= , f(q1 ,0)= q0,q1 f( q0,q1,0)= (q0 ,0) (q1 ,0)= q0,q1 f( q0,q1,1)= (q0 ,1) (q1 ,1)= q0,q1 M与M 的状态转换图如下所示： q0q0q1 0 0 1 1 1 start q0 q0 q0 q1 q0,q1

13、0 1 1 0,1 start 2.2.3 确定有限自动机的化简 所谓一个DFA M=(, S, S0, Z, f)的化简是指寻找一个 状态数比较少的DFA M,使 L(M)=L(M)。而且可以证明， 存在一个最少状态的DFA M, 使L(M)=L(M)。 自动机是描述信息处理过程的种数学模型 对一种语言，它可以用许多文法来描述，同样可以有无 限多个FA来描述一种语言；这些FA是等价的，但其构 成的复杂程度差别很大 一个DFA m是最小化的 它没有多余状态并且没有 互相等价的状态。 一个DFA m可以通过消除多余状态和合并等价状态 而转换成一个最小的与之等价的DFA m 一、有限自动机的多余状

14、态 （1）从该自动机的开始状态出发,任何输入串也不能 到达的那个状态 （2）从该状态出发没有通向终态结的道路 1 0 1 1 start q04 2 3 1 1 1 1 start q04 2 3 00 这些多余状态不在从初态到终态的路径上，对识别句 子无任何作用。 为什么？ 二、等价状态的定义 设p,q S ，若对任何w * ,f(p,w) 与 f(q,w) 同时到达终 止状态或拒绝状态之中 ，则称p和q是等价的。否则，称p和q 不等价（可区别）。 判定两个状态p和q不等价，只要找到一个w*， 使f （p,w)Z 且f（q,w) Z，或者相反。 说明 （a）终结状态与非终结状态不等价。 （b

15、）对于a ，f（p,a)=r, f（q,a)=s, r与s均等价，则p与q 等价; 若存在某个a ，f（p,a)=r, f（q,a)=s 其中r与s不等价, 则p 与q不等价。 设p表示非终结状态，q表示终结 状态， *， 使f（p, )=pZ 且f（q, )=q Z r与s不等价, 存在w* f（r, w) Z且f（s, w) Z f（p, aw) Z且f（q, aw) Z 分割法：把一个DFA(不含多余状态)的状态分割 成一些不相关的子集，使得任何不同的 两个子集状态都是可区别的，而同一个 子集中的任何状态都是等价的.在各个子 集中任取一个状态做代表，删去子集的 其余状态。 一个DFA m

16、可以通过消除多余状态和合并等价状态 而转换成一个最小的与之等价的DFA m 例:最小化 5 7 2 4 3 6 1 srart a a a a a a a b b b b b b b 分割法具体实现： 有没有多余状态？ 1 2 3 4 5 6 63 73 15 46 73 7 41 42 ab 子集 号 整理 1 2 3 4 5 6 63 73 15 46 73 7 41 42 1 2 ab 子集号 终结状态与非终结状态不等价 1 2 3 4 5 6 63 73 15 46 73 7 41 42 ab 1 2 4 3 子集号 1 2 4 3 1 2 3 4 5 6 63 73 15 46 73

17、 7 41 42 ab 5 子集号 1 2 3 4 5 6 63 73 15 46 73 7 41 42 ab 1 2 3 子集号 用子集号代替状态号得: 1 2 3 4 5 ab 52 14 35 52 31 1 5 5 24 3 a a a a a b b b b b 化简以下DFA q8q7q6q5 q1q2q3 1 1 1 1 0 11 1 0 0 0 0 0 0 q40 1 q8q7q6q5 q1q2q3 1 1 1 1 0 11 1 0 0 0 0 0 0 区分终态与非终态 整理 1 2 5 6 7 26 73 86 37 3 75 13 1 2 01 子集号 873 1 5 6

18、26 273 86 37 3 775 13 1 2 01 子集号 873 1 5 26 273 86 637 3 775 13 1 3 01 子集号 873 2 1 5 26 273 86 637 3 775 13 1 3 01 子集号 873 2 4 5 用子集号代替状态号得: 1 2 3 4 5 01 34 21 25 52 15 53 124 0 1 1 1 0 1 0 0 1 0 NFADFA 最小化 化简过程 正规文法与有限自动机（FA）的等价性 如果对于某个正规文法G和某个有限自动机M，有 L(G)=L(M) （正规文法G所产生的语言和某个有限自动机 所识别的语言相同）,则称G和M

19、是等价的。 定理2.2 对每一个右线性正规文法或左线性正规文法G， 都存在一个FA M，使 L(M)=L(G) 定理2.3 对于每一个FA M，都存在一个右线性正规文法G 和一个左线性正规文法G，使 L(M)=L(G)=L(G)。 正规文法 NFA DFA 最小化 有限自动机与正规文法 （1）有限自动机正规文法（右线性） 1.对转换函数f(A,t)=B，可写成一个产生式:AtB 算法: 2.对可接受状态Z,增加一个产生式:Z 3.有限自动机的初态对应于文法的开始符号, 有限自动机的字母表为文法的终结符号集. AB t 例:给出如图FA等价的正规文法G ABC D starta a a b b

20、b b G=（A，B，C，D，a，b， A， P） 其中P: A aB A bD B bC C aA C bD C D aB D bD D P: A aB A bD B bC|b C aA C bD|b D aB D bD|b （2）正规文法（右线性）有限自动机M 算法: 1.字母表与G的终结符号相同. 2.为G中的每个非终结符生成M的一个状态,G的开始符号S 是开始状态S; 3.增加一个新状态Z,作为NFA的终态 4.对G中的形如AtB,其中t为终结符或,A和B为非终结 符的产生式,构造M的一个转换函数f(A,t)=B 5.对G中的形如At的产生式,构造M的一个转换函数 f(A,t)=Z 例

21、:求与文法GS等价的NFA GS: SaA|bB| AaB|bA BaS|bA| S Z A B start aa a b b b 求得： 2.3 正规式（正规表达式）与有限自动机 2.3.1 正规表达式与正规集 2.3.2 正规式与有限自动机 2.3.1 正规表达式与正规集 正规表达式是一种表示法，可以详细描述高级程序语 言单词符号的结构或者说每一个正规表达式 r 表示一个语 言 L(r). 例如可以用正规表达式表示Pascal语言的标识符（描述 标识符的结构），而 Pascal语言的标识符（集合）可以看作 一个语言，因此正规表达式 r 实质是用来表示一个语言 L(r). Pascal语言的

22、标识符是字母开头的字母数字串，如何表示？ 正规表达式的递归定义 字母表上的正规表达式递归定义如下: 1. 和都是 上的正规表达式, 它们所表示的语言分别为:和 ; 2. 任何a , a是 上的正规表达式,它所表示的语言为:a; 3. 假定r和s是上的正规表达式, 它们所表示的语言分别记为L(r) 和L(s), 那么r|s, rs, r*也都是上的正规表达式,它们所表示的 语言分别为L(r)L(s)、 L(r)L(s)、L(r)* r|s L(r)L(s) rs L(r)L(s) r* L(r)* 一个由正规表达式表示的语言称为一个正规集 规定“*”， “连接” ，“”运算左结合， 优先级由高到

23、低 简化正规式 (a)(b) * (c) 等价于ab *c 例：=A,B,Z,a,b,z,0,1,9 正规式1：A B. Z a b. z 语言1：L( A) L( B) L( Z) L( a) L( b). L(z) = A,B,Z,a,b,z 正规式2： 0 1 . . 9 语言2：L(0) L(1) . L(9)= 0,1,9 例 =a,b (a) a b L(a) L(b)= a,b (b) (a b )(a b ) (L(a) L(b) (L(a) L(b) =aa,ab,ba,bb ( c) a* (L(a) )* = ,a,aa,aaa,aaaa, (d) (a b)* (L(a

24、) L(b) * = ,a,b,aa,ab,ba,bb,aaa,. (e) a a * b 符号串a和包括零个或多于零个a后跟一个b构成的所有 符号串 正规式： ( A B. Z a b. z) ( A B. Z a b. z) (0 1 . 9)* 语言： A,B,Z,a,b,z(A,B,Z,a,b,z 0,1,9)* letter(letterdigit)* A B. Z a b. z letter名字 letter是A, B,Z, a, b,z, 0, 1,9任意一个字母 0 1 2 3 . . 9 digit名字 digit是0, 1,9数字集合中任意一个数字 Pascal语言的标识符

25、 思考：C+语言的标识符? 恒等式 说明 rs=sr“”是可交换的 r(st)=(rs)t “”是可结合的 r(st)=(rs)t连接是可结合的 r(st)=rs rt (st)r=srtr 分配律 r=r r=r对连接，是单位元素 r*=(r)*“*”和之间的关系 r*=r*“*”是幂等的 正规表达式的代数性质 Kleene闭包r*：任意次的引用，若0次引用则为 正闭包r+：一次或多于一次的引用 r*=r+ r+= r r* 描述单词符号的结构，是进行词法分析程序设计的第一步 在表示的基础上如何做进一步的工作？ 2.3.2 正规式与有限自动机 定理2.5 设r是上一个正规表达式，则存在一个

26、FA m接受L( r )。反之亦然。 正规文法，正规表达式和有限自动机三者之间在某种意 义下是等价的。 字母表上的一个正规语言，既可以由某一个正规文法 产生，也可以由某一个正规表达式所表示，还可以由某一 个有限自动机识别。 正规文法 NFA正规表达式 DFA 最小化 1. r= 2. r= 3. r=a, a q0 q0q1q0q1 a r=r= r=a 1.构造法证明正规表达式与有限自动机等价 startstart start 1、并运算r=r1r2 q0 q1f1 f2q2 f0 m2 m1 r=r1r2 start r=r1r2r=r1r2r=r1* 2、连接运算 r=r1r2 q1f1

27、q2 m2 m1 f2 r=r1r2 start 3、闭包运算 r=r1* q0 f0q1f1 r=r1* m1 start 例 构造与 r=1* 等价的有限自动机。 q1q2 1 q1q2q4q3 1 start r=r1* q0 f0 q1f1m1 start 例 构造与 r=01* 等价的有限自动机。 q1q2q4q3 1 start q1q2 0 q1f1q2 m2 m1f2 r=r1r2 start 0 q0q1 q3q4q5q2 1 start q0 q1f1 f2q2 f0 m2 m1 r=r1r2 start 例 构造与 r=01*1 等价的有限自动机。 0 q0q1 q3q4

28、q5q2 1 start q1q2 1 q6q7 1 q8 q9 0 q0q1 q3q4q5q2 1 start 3 letter 12 4 5 letter 6 78 digit 9 10 start letter(letter|digit)* 2 letter letter 0 digit start 正规表达式NFADFA 最小化 化简过程 3 letter 12 4 5 letter 6 78 digit 9 10 start letter 1 start 2,3,4,5,7,10 4,5,6,7,9,10 4,5,7,8,9,10 letter digit digitletter l

29、etter digit 2 letter letter 0 digit start 对于上任一正规表达式r ，一定能构造一个NFA m ， 使得L( r )=L(m)。 首先对NFA m构造一个广义的转换图，其中只有开始状 态S和终止状态Z，连接S和Z的有向弧上是正规式R，然后 按照下面的替换规则对正规式不断进行分解，不断加入状 态结点和箭弧，直到转换图上的所有弧标记都是上的元 素或为止。 2. 转换法证明正规式与有限自动机的等价 ac ac ac r1r2 r1r2 r1r2*r3 替换规则 代之以 代之以 代之以 abc ac abc r1 r2 r2 r2 r1 r1 r3 从正规式到有

30、限自动机 设=x,y, 上的正规式R=xy*(xy|yx)x*，构造一个 NFA M，使L(M)=L(R). xy*(xy|yx)x* S Z start x S Z1 y* 2 xy|yx 3 x* x S Z1 3 xy 42 y yx 5 x x S Z1 3 x 62 y y 7 x y x 4 5 3 letter 12 4 5 letter 6 78 digit 9 10 start letter(letter|digit)* 2 3 letter letter 0 digit start 1 构造法 转换法 NFA？ 正规表达式NFADFA 最小化 化简过程 构造法 转换法 对于上任一NFA m，能构造上一个正规表达式r， 使得L( r )=L(m)。 把转换图的概念拓广，每条弧上可以用一个正规式标 记。首先，在m的转换图上加进S,Z两个结点。从S用弧 连接到m的所有初态结点，从m的所有终结（接受）结点用 弧连接到Z，从而构成一个新的NFA m，L(m)=L(m)。 反复使用下面的替换规则逐步消去NFA m中的状态结 点和弧，直至剩下S,Z为止。在消去结点的过程中，逐步用 正规式标记弧。 从正规式到有限自动机 从有限自动机到正规式 构造法 转换法 abc ac acac abc