编译原理：第2章 形式语言与自动机基础2

1、第 2 章 形式语言与自动机基础2.1 文法和语言2.2 有限自动机2.3 正规式与有限自动机 Ch2 形式语言自动机理论基础 2.2 自动机基础 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的FA（DFA）有限自动机（ FA）anaja3a2a1有限状态控制器输入带工作动作：读读头所指向的字符；据当前状态和读的字符改变控制器的状态；将读头向前移动。第 2 章 形式语言与自动机基础 2.2 有限自动机基础 2.2.1 确定的有限状态自动机(DFA) 2.2.2 非确定的有限状态自动机(NFA) 2.2.3 NFA确定化 2.2.4 DFA化简 Ch2 形式语言自动机理论

2、基础 2.2 自动机基础 定义2.24 一个确定的有限自动机M ( DFA M)是一个五元组M =（Q, , f, q0, Z） Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的FA（DFA） 确定的有限自动机（ DFA） ( DFA：Deterministic Finite Automaton ) 其中： Q：状态的有限集合，每个元素qi (qi Q) 称为一 个状态。 ：输入字符的有限集合(或有穷字母表)。 每个元素是一个输入字符。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的FA（DFA） q0：M的唯一初态（也称开始状态），q0Q。 f：

3、状态转换函数：从QQ的映射。 例如, f（p,a）=q, q、pQ, a。表示了在状 态p读入字符a后转入状态q。q也称为p的 后继状态。 Z： M的终态集（或接受状态集）ZQ。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的FA（DFA）二. DFA的等价表示 DFA形式定义 状态转换图 状态转换表 例2.20: DFA M = （0,1,2,3, a,b, f , 0 , 3） f（0,a）=1f（0,b）=2 f（1,a）=3f（1,b）=2 f（2,a）=1f（2,b）=3 f（3,a）=3f（3,b）=3Qq0Zf Ch2 形式语言自动机理论基础 2.2 自动

4、机基础 2.2.1 确定的FA（DFA） 状态转换图表示 DFA 状态图 Q 状态结点 弧上标记(边权值) f 带权值的有向边 q0 Z q0Z Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的FA（DFA）0123aabbab 状态转换图表示DFA M =(0,1,2,3, a,b, f , 0 , 3） f（0,a）=1 f（0,b）=2 f（1,a）=3 f（1,b）=2 f（2,a）=1 f（2,b）=3 f（3,a）=3 f（3,b）=3ab Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的FA（DFA）二. DFA的等价表示 DFA形式定

5、义 状态转换图 状态转换表 例2.20: DFA M = （0,1,2,3, a,b, f , 0 , 3） f（0,a）=1f（0,b）=2 f（1,a）=3f（1,b）=2 f（2,a）=1f（2,b）=3 f（3,a）=3f（3,b）=3Qq0Zf Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的FA（DFA） 状态转换表表示 a b 0 1 2 1 32 2 1 2 3* 3 3f Qq0ZDFA M =(0,1,2,3, a,b, f , 0 , 3） f（0,a）=1 f（0,b）=2 f（1,a）=3 f（1,b）=2 f（2,a）=1 f（2,b）=3 f

6、（3,a）=3 f（3,b）=3 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的FA（DFA）三 . DFA的识别机制 如果存在Q中的状态序列p0，p1，pn，满足下列条件： p0q0 f（pi，wi1）pi1，i0，1，n1 pnZ 则M接受（识别）。确定的有限自动机M=（Q, , f, q0, Z）接受或识别字母表上的字符串w1w2 wn 的意义： Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的FA（DFA）有限自动机（ FA）离散数字系统的抽象数学模型。# anan-1aja3a2a1确定的有限状态控制器输入带(q0)(p1)(p2)(pj

7、-1)(pn-2)(pn-1)(pn)确定的有限自动机M=（Q, , f, q0, Z）接受或识别字母表上的字符串w1w2 wn 的意义：根据串沿着序列（路径）p0，p1，找到pn，判断pn是否属于终态集。判断寻找 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的FA（DFA）具体识别方法：如果存在Q中的状态序列p0，p1，pn，满足下列条件： p0q0 f（pi，wi1）pi1，i0，1，n1 pnZ 则M接受（识别）。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的FA（DFA）从状态图出发可以更形象地进行描述。若存在一条从初态结点开始的弧上的

8、标记连接成字符串的路径，且路径终点为终态结点，则称被该DFA M所识别(接受)。确定的有限自动机M识别的字符串的全体称为M识别的语言，记为L(M)。 L(M) = | * f(q0, ) Z 特例的是，若M的初态结点同时又是终态结点，则空串为M所识别。设a1a2an-1an，f(q0,)=f(f(f(f(q0,a1,),a2),an-1),an) Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的FA（DFA） 例2.21: 分析下面描述的DFA M1 。DFA M1=(qee, qoe, qeo, qoo，0,1，f，qee，qee) 其中：f(qee ，0)= qoe

9、f(qee ，1)= qeof(qoe，0)= qee f(qoe，1)= qoof(qeo，0)= qoo f(qeo，1)= qeef(qoo，0)= qeo f(qoo, 1)= qoe Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的FA（DFA） $1=110101，M1对$1的识别过程是：f（ qee ,1）= qeo f（ qeo ,1）= qee f（ qee,0）= qoef（ qoe , 1）= qoo f（ qoo ,0）= qeo所以串$1= 110101可以被M1接受。(qee,qoe,qeo,qoo,0,1,f,qee,qee) f(qee ,

10、0)= qoef(qee,1)= qeof(qoe,0)= qeef(qoe,1)= qoof(qeo,0)=qoof(qeo,1)= qeef(qoo,0)=qeo f(qoo,1)= qoef（ qee , 110101 ）= f(f（ qee ,1）, 10101)= f（ qeo ,1）= qeeZf（ qeo ,1）= qeeZ Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的FA（DFA） DFA M1状态图1qeeqeoqoeqoo1110000对1010: 1010对11001:qee qeo qee qoe qee qeo所以串11001被该DFA拒绝！

11、10011qee qeo qoo qoe qee所以串1010被该DFA接受！Z 可以识别的语言为含偶数个0和偶数个1的二进制串集合。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的FA（DFA） 例2.22: 设计一台DFA ，接受含有子串001的所有二进制串。 问题分析： 输入字母为0或1，所以0,1扫描过程中有4种可能性：开始寻找001；读到一个0；读到到00；读到了001所以有4个状态Qq，q0， q00， q001,其中q为初态，q001为终态。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的FA（DFA）qq0q00q00100111

12、00,1代表两条有向边，一个权值为0，一个为1接受含有子串001的所有二进制串的DFA 与文法等价概念类似： 设有DFA M 和DFA M ， 若L(M) = L(M) , 则称M 和 M 等价。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的FA（DFA） 注意： 1） DFA是具有离散输入、输出系统的一 个纯数学模型； 2） DFA的技巧在于状态的设置； 3） DFA映射的唯一性。（ 对于任意字, 在DFA中有且仅有唯一路径）。第 2 章 形式语言与自动机基础 2.2 有限自动机基础 2.2.1 确定的有限状态自动机(DFA) 2.2.2 非确定的有限状态自动机(N

13、FA) 2.2.3 NFA确定化 2.2.4 DFA化简 Ch2 形式语言自动机理论基础 2.2 自动机基础 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.2 非确定的FA(NFA)一. NFA的定义 DFA的确定性表现在其映射函数是一个单值函数。但是实际问题中，映射函数往往是一个多值函数。 例如，源程序中扫描到一个字母时，不同的语言对应多种情况：FORTRAN中： 标识符/格式转换码E、D C语言中：标识符/ if / switch . Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.2 非确定的FA(NFA) 例如， + C语言中： + += NFA在实际中更具普

14、遍性。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.2 非确定的FA(NFA) 定义2.25 一个非确定的有限自动机M ( NFA M)是一个五元组M =（Q, , f, q0, Z） 其中： Q， ， Z， q0同DFA。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.2 非确定的FA(NFA) f：状态转换函数。 从Q( ) 2Q的映射。这里的后继状态不是唯一的，它是状态集Q的子集。 注意：NFA亦可用状态图和状态表表示。DFA和NFA统称为有限自动机FA。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.2 非确定的FA(NFA) 例2.23:

15、设有一个非确定的有限自动机M NFA M=（q0, q1, q2, q3, q4,0,1, f , q0, q2,q4） 其中状态转换函数f为： f(q0，0)= q0,q3 f(q0，1)= q0, q1 f(q0，)= f(q1，0)= f(q1，1)= q2 f(q1，)= f(q2，0)= q2 f(q2，1)= q2 f(q2，)= f(q3，0)= q4 f(q3，1)= f(q3，)= f(q4，0)= q4 f(q4，1)= q4 f(q4，)= QZq0 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.2 非确定的FA(NFA) 0 1 q0 q0,q3 q0,q

16、1 q1 q2 q2* q2 q2 q3 q4 q4* q4 q4 状态子集q1q3q4q2q000110,10,10,1f（q0,0）= q0,q3 f（q0,1）= q0,q1 f（q1,0）= f（q1,1）= q2 f（q2,0）= q2 f（q2,1）= q2 f（q3,0）= q4 f（q3，1）= f（q4,0）= q4 f（q4,1）= q4 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的FA（DFA）二 . NFA的识别机制 如果存在Q中的状态序列p0，p1，pn，满足下列条件： p0q0 pi1f（pi，wi1），i0，1，n1 pnZ 则M接受（识

17、别）。非确定的有限自动机M=（Q, , f, q0, Z）接受或识别字母表上的字符串w1w2 wn ， wi 的意义： Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的FA（DFA）从状态转换图进行描述：若存在一条从初态结点开始的所有弧的标记连接成字符串的路径，且路径终点为终态结点， 则称被该NFA M所识别(接受)。非确定的有限自动机M识别的字符串的全体称为M识别的语言，记为L(M)。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.2 非确定的FA(NFA) 例2.23的非确定的有限自动机M所识别的语言L（M）？ L（M）含有两个相邻的0或两个相邻的1的由

18、0和1组成的字符串q1q3q4q2q000110,10,10,1 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.2 非确定的FA(NFA)例2.24: 给出一个识别语言为a+ b+的NFA M 如下图所示。bba0413 2a对字符串aaa的识别路径：aaa 1 2 2 2Z 0 3 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的FA（DFA） 例2.22: 设计一台FA ，接受含有子串001的所有二进制串。 问题分析： 输入字母为0或1，所以0,1扫描过程中有4种可能性：开始寻找001；读到一个0；读到到00；读到了001所以有4个状态Qq，q0， q0

19、0， q001,其中q为初态，q001为终态。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.1 确定的FA（DFA）qq0q00q001001接受含有子串001的所有二进制串的FA 0,10,1 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.2 非确定的FA(NFA) NFA DFA f ( Q ) f ( Q ) f f (Q ) 2Q f ( Q) Q 三. NFA和DFA的区别 注意：在NFA中对字的识别时验证的路径可能不唯一。第 2 章 形式语言与自动机基础 2.2 有限自动机基础 2.2.1 确定的有限状态自动机(DFA) 2.2.2 非确定的有限状态自

20、动机(NFA) 2.2.3 NFA确定化 2.2.4 DFA化简 Ch2 形式语言自动机理论基础 2.2 自动机基础 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.3 NFA确定化 定理2.1 对任何一个NFA M，都存在一个DFA M , 使 L(M )=L(M)。 定理2.1说明： 对任何一个NFA M，都存在一个DFA M ，使M和M所识别的字的全体相同，我们可简记为 M M。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.3 NFA确定化 NFA确定化的算法 子集法。 定义2.26 假设I是NFA M 状态集Q的一个子集。(即IQ)，则定义-closure(

21、I)为 ： (1)若qiI，则qi -closure(I)； (2) 若qi I，则从qi出发经过任意条弧而能到达 的任何状态qj ，有qj -closure(I)。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.3 NFA确定化 设 I= 1,5 则 -closure(1,5) -closure (1) -closure (5) 1,2,5,6 设 I=5 设 I=1 则 -closure(I) = -closure(5) = 5, 6, 2则 -closure(1) = 1, 21238546 7aaa 例2.25:有NFA M如右图所示。 Ch2 形式语言自动机理论基础 2

22、.2 自动机基础 2.2.3 NFA确定化 综述：1）状态集I的-closure(I)仍是一状态集； 2） 状态集（-closure(I)）即为在I中的状态 下，不输入任何字符所能到达的状态的 全体并包含I中的状态，就是状态集I的 闭包。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.3 NFA确定化 算法2.1 (求I的-closure(I) 输入：NFA M 和M的子集I 输出：-closure(I) 算法： set_of_state look (set_of_state I) look=I; do 对look中每一个状态i if 结构 look = look + j; wh

23、ile(look不再扩大) ij Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.3 NFA确定化 定义2.27 （状态集合I的a弧转换Ia ） 设 NFA M =(Q，f，q0，Z) 假定I Q，a，则定义 Ia=-closure(p|q -close(I)，pf(q，a)。 注意：计算Ia需三步： I的闭包；闭包的映射集；映射集的闭包。Ia=-closure(f ( -close(I) ，a)。设I=2,5 则 Ia =-closure（f(2,5,6,a） =-closure（3）= 3,8 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.3 NFA确定化例2.2

24、6: 有NFA M如例2.25。 设I=1 求Ia 则-closure（I）1, 2 f(1,2,a)=f(1,a)f(2,a) =3,4,5 Ia =-closure（3,4,5） = 2, 3, 4, 5, 6,7,8 1238546 7aaa Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.3 NFA确定化 NFA确定化关键： 1） 消去弧； 2） 解决映射不唯一问题。-closure(I)求Ia Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.3 NFA确定化 子集法NFA的确定化算法 对NFA M =（Q, 1, 2, , n , f, q0, Z）I I 1

25、 I 2 I n -closure(q0)Step1:初始化 设一状态表： Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.3 NFA确定化I I 1 I 2 I n -closure(q0)I11I12I1nI11I12I1nStep2:求InI2nI3nI2i Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.3 NFA确定化 Step3: 重新命名 对求得的状态表（DFA M）的第一列各状态子集重新命名为状态，然后代入相应的状态表元素； 第一列第一行为DFA M 的惟一初态； 含有原M终态的I为M终态。-closure(q0) Ch2 形式语言自动机理论基础 2.2

26、 自动机基础 2.2.3 NFA确定化I Ia2, 3, 4, 5, 6, 7, 8 3, 81 201 22, 3, 4, 5, 6, 7, 8 3, 81238546 7aaa *例2.27:将右图所示NFA M 确定化。1,2 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.3 NFA确定化a0 1* 2*122138546 7aaa 012aaI I0 I1 p q, s q q, s q r r q,r,p r q,r,p q,r q,r s p s q,r,s q,r,s q,r,p r,s r,s r,s q,r,p q,r,p p p s 0*123 4*56781

27、3367886245044040 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.3 NFA确定化1rqs0,10,10101p1例2.28: 将右下图所示NFA M 确定化。state 0 1 0*123 4*567813367886245044040 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.3 NFA确定化1prqs0,10,10101p1第 2 章 形式语言与自动机基础 2.2 有限自动机基础 2.2.1 确定的有限状态自动机(DFA) 2.2.2 非确定的有限状态自动机(NFA) 2.2.3 NFA确定化 2.2.4 DFA化简 Ch2 形式语言自动机理

28、论基础 2.2 自动机基础 所谓DFA M的化简是指寻找一个状态数最 少的DFA M（规约或最小的DFA M ）， 使得L(M)=L(M)。 已证明存在一个最小DFA M，使得 L(M)=L(M)。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.4 DFA的化简 定义2.28 如果DFA M既没有无关状态，且没有彼此等价的状态，则称DFA M是规约的(即最小的DFA M)。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.4 DFA的化简 定义2.29(无关状态或多余状态或无用状态) 如果从DFA M的初态开始，任何输入序列都不能到达的那些状态称为无关状态。 DFA化

29、简实现思想： 通过删除无关状态，合并等价状态的规约过程，直至得到规约机( 最小的DFA )。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.4 DFA的化简(1) 标记开始状态q0；(2) while（存在未处理的标记状态） 取未处理的标记状态q，标记为处理， 对所有a， 若f(q，a)p，且p未标记，标记p； (3) 删除未标记的状态及与其相关的转换。删除DFA无关状态的算法： Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.4 DFA的化简 0 1 state638107086135654753522721510例2.29: 有FA M考察：0：从状态0开始，经过

30、输入0或1 1，5；015 从状态1开始，经过输入0或1 2，7；27 从状态5开始，经过输入0或1 3，1；3 从状态2开始，经过输入0或1 2，5； 从状态3开始，经过输入0或1 5，7； 从状态7开始，经过输入0或1 0，1；1：5：2：7：3：从初态0开始，4,6,8是不可到达的状态。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.4 DFA的化简 0 1state012357122530575711 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.4 DFA的化简定义2.30 (等价状态、可区分状态) 设DFA M的两个不同状态 q1，q2，如果对任意输入字

31、符串，从q1，q2状态出发，总是同时到达接收状态或拒绝状态之中，称q1，q2是等价的。即对于，(*)有：f(q1，)= p1 ， f(q2，)=p2 ，p1 ,p2Z 或p1 ,p2Z ，则q1，q2等价，记作 q1q2 。如果两个状态不等价，则称q1，q2是可区别的（或者说q1，q2 被 所区别）。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.4 DFA的化简 DFA合并等价状态的实现方法：划分法。 划分法的核心是寻找且合并等价状态。即：将给定的DFA划分为互不相交的子集，使得任何两个不同子集的状态都是可区分的，而同一个子集的任何两个状态都是等价的。然后每个子集中的状态合并为

32、一个状态。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.4 DFA的化简 划分法的算法实现步骤如下： (1) 把M的所有状态Q按终态与非终态划分成两个状 态子集Z及QZ，构成初始划分(或称基本划分)， 记作：= Z, QZ ；(2)设当前的划分中已经含有m个子集，即： = Q1，Q2，Qm 其中，属于不同子集的状态是可区分的，而属于同一子集中的各状态是待区分的。即需要对每一个子集Qi=qi1，qi2，qin中各状态qir (qirQ, 1rn) 进行考察，确认是否还能对它们进行划分。 若能进行划分，则形成新的划分new 。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2

33、.2.4 DFA的化简(3) 若new，则将其作为再重复(2)中的过程，如此下去，直到最后得到一个划分，使new，即中的各个子集不能再进行划分为止。(4)对所得的最后划分，对它的每个子集Qj =qj1，qj2，qjr进行重新命名为一个状态，如pj作为 中子集Qj的名字，这些新命名的状态pj组成了M 的状态集Q 。并且，若Qj中含有M的初态,则pj为M 的初态;若Qj中含有M的终态，则pj为M 的终态。此外，对状态转移函数作相应的修改。第（2）步详解：例如，qir和qis是Qi中的两个状态，若有某个a,使得f (qir, a)= qju 及f (qis, a)= qkv，而状态qju 及qkv分

34、别属于中两个不同的子集Qj和Qk，由于qju 与qkv为某一符号串所区分，从而qir和qis必为a所区分，故应将子集Qi进一步划分，使qir和qis分别属于Qi的不同子集。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.4 DFA的化简(2)需要对每一个子集Qi=qi1，qi2，qin中各状态qir (qirQ,1rn) 进行考察，确认是否还能对它们进行划分。第（2）步需要考察：对于每一个子集Qi及每一个a， Qia= f (Qi , a) = f (qir, a)若Qia中的状态分别落在中的p个不同的子集，则将Qi分为p个更小的状态子集Qi1，Qi2 ，Qip，若f (Qi ,

35、a)中的全部状态都落在的同一子集之中，则不再划分Qi。特殊情况：若对某状态qir，f (qir, a)无意义，则qir与任何f (q, a)有定义的状态都是可区分的。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.4 DFA的化简 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.4 DFA的化简例2.30： 设确定有限自动机DFA M ，如图所示。 Step1: 形成基本划分。划分为终态集和非终态集。 P0 = （ 0,1 , 2） 不可对 0,1 再分Step2: 重新命名。令 0,1为0，令2为1。babaa021考察 ： f(0,a)=1 0,1 f(1,a)=

36、1 0,1f(0,b)=2 2f(1,b)=2 2 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.4 DFA的化简化简后的DFA M 1 0ababaa021ba重新命名： 0,1为0，2为1。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.4 DFA的化简例2.31：对下图的DFA M化简。aaaabbababb 1a 6 4 3 7 5b 2b Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.4 DFA的化简第一步，对M的状态形成基本划分，有两个组q1 , q2，即 = ( q1,q2 ) =(1, 2, 3, 4 , 5, 6, 7 )第二步，考察 中的q: f(1,a)=6 q2 f(2,a)=7 q2 f(3,a)=1 q1 f(4,a)=4 q1 1423576abaaaaaabbbbbb输入a的情况下， q1中的状态1,2与状态3,4 是不等价的。 Ch2 形式语言自动机理论基础 2.2 自动机基础 2.2.4 DFA的化简 对q1进行划分，形成： q1