第3 章 有穷状态自动机 在乔姆斯基体系中,根据文法的不同,语言被分成4类。在这里,语言的文法描述提供 了生成语言的手段,但是,对语言句子的识别来说,还存在一些不方便。从本章开始,将按照 语言的分类,介绍一些识别语言的模型。 3.1 语言的识别 第2章定义由正则文法产生的语言为正则语言。当给定一个正则文法G=(V,T,P,S), 相应的正则语言L(G)也就给定了。此时,任意给定一个字符串w,w 是这个语言的句子吗? 为回答这个问题,需要考查S.* w 在G 中是否成立。按照文法的要求,如果w 能由给定文法 产生,就必须找出它的推导,或者将它归约成S;如果w 不能由文法产生,就必须证明G 中不 存在w 的推导,或者w 在G 中不能归约成S。这件事并不是对所有的文法都很容易做到的, 正则文法也不例外。在第2章中已经了解到,给定文法所定义的语言的一个句子在该文法中 可能存在许多不同的推导。更为严重的是,有时可以选择的直接推导不止一个,它们中有的是 对的,有的是错的。如果选择了错误的推导,则在后续的推导中发现错误而无法继续进行下去 时,就需要回过头来重新选择推导。归约也是一样,也会在某一步遇到多个不同的直接归约, 它们中间也可能存在当前看似正确而实际是错误的归约。当不幸选中错误的归约,同样需要 回过头来重新进行选择。这个过程称为“回溯”,是高级程序设计语言编译系统的设计中要解 决的重要问题之一。当w 不能由文法产生时,必须证明G 中不存在w 的推导,或者w 在G 中不能归约成S。也就是说,要证明所有的推导都无法得到w,或者所有的归约都不能将w 最终归约成S。下面看一个简单的例子。设文法G 有如下产生式: S →aA |aB A →aA |c B →aB|d 字符串aaad 是该文法所定义的语言的句子吗? 现在按推导的方法来回答此问题,归约方 法类似,请读者自己练习。 一般系统在处理当前字符时,并不知道后面将出现的字符,所以,对字符串aaad 的分 析,一开始并不知道句子的尾字符是d。除非通过多遍扫描来完成句子的分析,否则就难以 保证推导的每一步一定都是该句子的正确推导。只有在多遍扫描中,才有可能在进行句子 形式语言与自动机理论(第4版) 的推导前收集到可用于推导的信息。假设在推导的第一步选择 S 产生式的第一个候选式, 于是 S.aA 使用产生式S→aA .aaA 使用产生式A→aA .aaaA 使用产生式A→aA .aaaaA 使用产生式A→aA 到这里,才发现这一推导无法推出ad。首先要考虑的问题是在上述推导中是否有选择错 24=16 种“需要考虑的”不同推导,注意仅仅在这种意义下的推导已经是文法的语法变量的 候选式个数的推导步数次幂), 而我们只选择了其中的一种。是第四步应该用产生式A→ c 吗? 要回答此问题,需要回到第三步推导的结果: 误的时候,因为上述推导的每一步(a) 各有两个不同的产生式可供选择(这样,共有(a) .aaaA 使用产生式A→aA .aaac 使用产生式A→ c 结果仍然不对,因此又要重新回到第二步的推导结果…… 如此下去,最后回到开始,使用产 生式S→aB 重新开始推导。由此出发,读者自己不难给出aaad 的正确推导(仍然会出现 错误的推导)。 由上例可以看出,推导和归约中的回溯问题将对系统的效率产生极大的影响。是否可 以从识别的角度去考虑问题的求解呢? 不难看出,上例中文法 G 产生的语言的句子都是前 面至少有一个a,最后是一个 c 或者是一个d,最后一个字符是 c 的可以算一类,最后一个字 符是 d 的可以算另一类: |a nn {acn≥1}∪{d|n≥1} 现在考虑按照如下方式设计一个系统:系统初始时处于开始处理输入字符串的状态(不妨 取名为q0)。当读入一个 a 时,表示输入串已经满足 a 的个数“至少为1”的要求(至(“) 少为 1” a 的个数可以有多个), 可用一个状态表示目前已经得到至少一个a(不妨取 表明,因此, 名为q1)。在q1 状态下,如果遇到a,仍是满足至少一个 a 的要求,系统保持在q1 状态;如 果遇到c,则表示当前接受的字符串属于第一类,系统进入状态q2;如果在q1 状态下遇到 d,则表示当前接受的字符串属于第二类,系统 进入状态q3。为了实现对该系统(模型)既简洁 (抽象)又直观的描述,用顶点表示系统的状态, 用带有标志的弧表示系统在某一状态下从输入 字符串中读入当前字符后进入到另一个状态。 27 图3-1 na nac 系统识别语言{|n≥1}∪{ d|n≥1} 据此,得到图3-1。 的字符串过程中状态的变化图示 根据图3-1,系统对字符串aaad 的处理就 相对“容易”一些:系统在状态q0 启动(用标有 S 的箭头表示), 读入字符a,转到状态q1,在 q1 状态下,读入第二个字符a,系统仍然处于状态q1;再读入第三个字符a,系统仍然处于状 态q1;读入第四个字符 d 时,系统进入状态q3。到此,发现aaad 是语言中的第二类句子。 如果输入的字符串中还剩余有其他字符,那么这个输入字符串就不是该语言的句子了。这 里用双圈顶点表示获得给定语言句子的状态。也就是说,系统在处理输入字符串的过程中, 如果能从初始状态开始,最后到达用双圈顶点表示的“终止”状态,就认为这个输入字符串是 有穷状态自动机 第 给定语言的句子;否则,这个输入字符串就不是给定语言的句子。虽然这种系统(模型)每 3 “启动一次”只完成一个句子的识别,但是它可以识别语言的所有句子。所以,可以称这种系 章 统(模型)为语言的识别系统(模型)。 对上述识别系统(模型), 可以归纳出如下几个主要方面: 37 (1)系统具有有穷个状态,不同的状态代表不同的意义。按照实际的需要,系统可以在 不同的状态下完成规定的任务。 (2)可以将输入字符串中出现的字符汇集在一起,构成一个字母表。系统处理的所有 字符串都是这个字母表上的字符串。 (3)系统在任何一个状态(当前状态)下,从输入字符串中读入一个字符,根据当前状态 和读入的这个字符转到新的状态。当前状态和新的状态可以是同一个状态,也可以是不同 的状态。当系统从输入字符串中读入一个字符后,它下一次再读时会读入下一个字符。这 就是说,系统有一个读写指针,该指针在系统读入一个字符后指向输入串的下一个字符。 (4)在所有的状态中有一个状态,它是系统的开始状态,系统在这个状态下开始进行某 个给定句子的处理。 (5)还有一些状态表示系统到目前为止所读入的字符构成的字符串是语言的一个句 子,将系统从开始状态引导到这种状态的所有字符串构成的语言就是系统所能识别的语言。 将此系统(模型)对应成如图3-2所示的物理模型———称之为有穷状态自动机的物理模 型。首先,它有一个输入带。该输入带上有一系列的“带方格”,每个带方格可以存放一个 字符。为了不让输入带的存储容量影响我们对主要问题的考虑,约定:输入串从输入带的 左端点开始存放,输入带的右端是无穷的。也就是说,从左端点的第一个带方格开始,输入 带可以存放任意长度的输入字符串。其次,系统有一个有穷状态控制器(finitestate control,FSC), 该控制器的状态只有有穷多个。FSC 控制一个读头,用来从输入带上读入字 符。每读入一个字符,就将读头指向下一个待读入的字符。 图3- 2 有穷状态自动机的物理模型 系统的每一个动作由3个节拍构成:读入读头所指向的字符;根据当前状态和读入的 字符改变有穷控制器的状态;将读头向右移动一格。 3.有穷状态自动机 2 CPU 、存储器、外部设备组成的基本的计算机硬件系统可以表示成三元组 : 计算机硬件系统=(CPU,存储器,外部设备 ) 47 形式语言与自动机理论(第4版) 进程管理、设备管理、存储管理、文件管理、网络通信管理组成的计算机操作系统可以表示成 五元组: 操作系统=(进程管理,设备管理,存储管理,文件管理,网络通信管理) 同样,将有穷状态自动机表示成一个五元组(quintuple或5-tuple),其形式化的定义如下。 定义31 有穷状态自动机(n, M 是一个五元组: finiteautomatoFA) M =(Q,δ,F) Σ,q0, 其中,Q—— inputalphabeq 称为 M 的一个状态(stat —状态的非空有穷集合。.q∈Q,e)。 Σ———输入字母表(t)。输入字符串都是 Σ 上的字符串。 δ——tastoucin), δ: —状态转移函数(rniinfnto有时又称为状态转换函数或者移动函数, Q×Σ→Q。对.(a)∈Q×Σ,q,=将状 q,δ(a) p 表示 M 在状态 q 读入字符a, 态变成p,并将读头向右移动一个带方格而指向输入字符串的下一个字符。 —— M 的开始状态(也可称为初始状态或者启动状态, q0—initialstate), q0∈Q。 F——fnlsae) F.Q。.q∈F, — M 的终止状态(iatt集合, q 称为 M 的终止状态。 应当指出的是,虽然将 F 中的状态称为终止状态,并不是说 M 一旦进入这种状态就终 止了,而是说 M 一旦在处理完输入字符串时到达这种状态, M 就接受当前处理的字符串。 所以 例31,有时又称终止状态为接受状态(aceptstate)。 下面是有穷状态自动机。 q2},{δ1,q2}) M1=({q0,q1,0},q0,{ 其中,q0,=q1,q1,=q2,q2,=q1, -。 δ1(0)δ1(0)δ1(0)可以用表31表示状态转移函数δ1 表3- 1 状态转移函数δ1 状态说明状态 输入字符 0 开始状态q0 q1 q1 q2 终止状态q2 q1 M2=({q0,q1,q2,q3},{0,1,δ2,q0,{ 2},q2}) 其中,=q1,q1,=q2,q2,=q1,q3,=δ2(1)q3,q1,= δ2(q0,0)δ2(0)δ2(0)δ2(0)q3,q0,=δ2(1) 1)=δ2(1)δ2(2)δ2(2)=δ2(2)δ2(2)=q3。 q3,δ2(q2,q3,q3,=q3,q0,=q3,q1,q3,q2,=q3,q3, 注意到用表格表达 δ 比逐个列出它的函数式更为清楚,所以,仍然采用表格的形式给出 δ2,如表3-2所示。 定义FA的目的是用它来识别语言,所以,需要将 δ 的定义域从 Q ×Σ 扩充到Q×Σ* 上。按照本节前面的描述,对一个给定的输入字符串, M 从开始状态读入该串的第一个字 符,每处理完一个字符,就进入下一个状态,并在此新状态下读入下一个字符。按照这个过 程,直到整个字符串被处理完。因此, 将 δ 扩充为 δ →Q。 按照下列定义, ^:Q×Σ* 有穷状态自动机 第 表3- 2 状态转移函数δ2 3 章 57 状态说明状态 输入字符 0 1 2 开始状态q0 q1 q3 q3 q1 q2 q3 q3 终止状态q2 q1 q3 q3 q3 q3 q3 q3 对任意q∈Q,w∈Σ*, 有 (^(ε)。 a∈Σ, 1)δq,= q ^(^( (2) δ wa)δw),)。 q,=δ(q, a ^ 由于 δ 的定义域Q×Σ 是 δ 的定义域Q×Σ*的真子集:Q×Σ.Q×Σ*,所以,对于任 意(a)∈Q×Σ,^ 和 δ 都有相同的值,就不用区分这两个符号了。事实上,对于任 q,如果 δ 意q∈Q,a∈Σ,有 ^(q,a)^( ^( a) ε 是单位元素 =δ(q,a) 2) q, δ =δε δε),根据定义的第(条 =δ(a) 1)条 q,根据定义的第( 所以,今后用 δ 代替 δ ^ 。 另外,由于对于任意q∈Q,δ(a) 所以 , a∈Σ,q,均有确定的值, 又将这种FA 称为确定 的有穷状态自动机(deterministicfiniteautomaton,DFA )。到此,可以给出DFA 接受的语 言的定义。 Q,δ,F) 如果δ(x)∈F, 定义32 设 M =(Σ,q0,是一个DFA 。对于.x∈Σ*, q0,则 q0, 称 x 被 M 接受;如果δ(x).F,则称 M 不接受x。 L( M )x|x∈Σ* q0, 称为由 M 接受(识别)的语言。 ={且δ(x)∈F} 不难看出,例31中定义的M1=({q1,0},q0,{和M2=({q1, -q0,q2},{δ1,q2}) q0,q2, q3},{0,2},q0,{所接受的语言为 1,δ2,q2}) L(M1)=L(M2)={02n|n≥1} 例32 定义33 设M1 和M2 为FA 。如果L(M1)=L(M2), 则称M1 与M2 等价。 构造一个DFA,它接受的语言为{y|x,0,*}。 x000y∈{1} 设L={x000y|x,y∈{0,1}*}。不难看出,这个语言的特点是“每个句子都含有3个 连续的0”。显然,对任意给定的一个输入x∈{0,1}*,所构造的DFA 的主要任务是检查 x 中是否存在子串“000,(”) 一旦发现它含有这样的子串,就表示它是一个合法的句子。所以,在 确认它含有“000”后,就应该逐一地读入该输入字符串的剩余后缀,并接受该串。所以,主要 问题是如何发现子串“000”。由于字符是逐一被读入的,当从输入串中读入一个0时,它可 能是子串“000”的第一个0,因此,需要记住这个0;如果紧接着读入的是1,则刚才读入的 67 形式语言与自动机理论(第4版) “0”并不是子串“000”的第一个0,此时需要重新寻找子串“000”的第一个0;如果紧接着读入 的是0,则这个0可能是子串“000”的第二个0,此时也需要记住这个0,且目前已经发现了 连续的两个0。DFA 继续向前扫描,如果再次读到0,则表明已发现子串“000”。按照这一 分析,识别所给语言的DFAM 至少需要如下几个状态: q0——— M 的启动状态。 q1——— M 读到了一个0,这个0可能是子串“000”的第一个0。 q2——— M 在q1 后紧接着又读到了一个0,这个0可能是子串“000”的第二个0。 q3——— M 在q2 后紧接着又读到了一个0,发现输入字符串含有子串“000”。因此,这个 状态应该是终止状态 。 从而,可得到关于 M 的状态转移函数的如下部分定义 : δ(0)q1—— M 读到了一个0, 000的第一个0 。 q0,=—这个0可能是子串“” δ(0)q2—— M 又读到了一个0, 000的第二个0。 q1,=—这个0可能是子串“” δ(q2,0)=q3——— M 找到了子串“000”。 q1,之所以说这只是 M 的状态转移函数的部分定义,是因为还缺乏当 M 在状态q0,q2 遇到 输入字符1时,以及 M 在状态q3 遇到0和1时的定义。所以,上述3项定义实际上给出了 M 的“主体框架”。现在将缺少的部分补充如下: δ(q0,1)=q0——— M 在q0 读到了一个1,它需要继续在q0“等待”可能是子串“000”的第 一个0的输入字符0。 δ(1)q0—— M 在刚刚读到了一个0后, 表明读入这个1之前所读 q1,=—读到了一个1, 入的0并不是子串“000”的第一个0。因此, M 需要重新回到状态q0,以寻找子串“000的(”) 第 一个 δ0( 。 1)q0—— M 在刚刚发现了00 后, 表明读入这个1之前所读入的 q2,=—读到了一个1, 00 并不是子串“000”的前两个0。因此, M 需要重新回到状态q0,以寻找子串“000的(”) 第一 q3,=—000, δ(q3,1)=q3——— M 找到了子串“000,(”) 只用读入该串的剩余部分 。 到此,得到接受语言{y|y∈{0,1} * 个0 δ。 (0)q3—— M 找到了子串“”只用读入该串的剩余部分。 x000x,}的DFA: M =({q1,q3},{0,1},{(0)q1,q1,=δ(0)q3,q0,= q0,q2,q0,=δ(0)q2,q2,=δ(1)q0, δ(1)q0,q2,=δ(0)q3,q3,=q3},q3}) q1,=δ(1)q0,q3,=δ(1)q0, { 为清楚起见,用表3-3表示该 M 的移动函数 。 表3- 3 M 的移动函数 状态说明状态 输入字符 0 1 开始状态q0 q1 q0 q1 q2 q0 q2 q3 q0 终止状态q3 q3 q3 有穷状态自动机 第 初学者容易忽视的问题是漏填表中某些定义项,尤其当以函数式和状态转移图(定 3 义3-4)的形式给出DFA 时更是如此。所以,特别强调:如果要求构造DFA,就必须给出所 章 有的定义,也就是要将表3-3填满,除非给出新的约定。 另外,若DFA 在扫描完输入串之前已经获得足够的信息,确认一个输入字符串是它接 受的句子,则它进入终止状态,并且可以在此状态读完该字符串的剩余部分。 下面用图3-3给出所构造的 M 的图示。 77 图3- 3 DFAM 的图示 这个图看起来要比 M =({q1,q3},{1},{q0,=δ(0)q2,q2,= q0,q2,0,δ(0)q1,q1,=δ(0) q3,q0,=δ(1)q0,q2,=δ(0)q3,q3,=q0,{直观得 δ(1)q0,q1,=δ(1)q0,q3,=δ(1)q3},q3}) 多,所以理解起来也容易许多。因此,将这种图定义为FA 的状态转移图。注意,这里定义 的状态转移图不仅仅用来表示DFA,还被用来表示后面定义的NFA 和ε-NFA 。 定义34 设 M =(Q,Σ,q0,为一个DFA,满足如下条件的有向图称为 M 的状态 转移图(rnsiiondar: δ,F) tatigam) (1)q∈Q. q 是该有向图中的一个顶点 。 (2)δ(a)p.图中有一条从顶点 q 到顶点 p 的标记为 a 的弧。 q, = (3)q∈F.标记为 q 的顶点用双层圈标出 。 (4)用标有 S 的箭头指出 M 的开始状态。 状态转移图又称为状态转换图。有时,状态转移图中会存在一些并行的弧:它们从同 一顶点出发,到达同一个顶点。对这样的并行弧,用一条有多个标记的弧表示。例如,图3-3 中的从状态q3 到状态q3 的标记为0和1的弧表示从状态q3 到状态q3 有两条并行的弧, 它们的标记分别为0和1。 例33 构造一个DFA,它接受的语言为{x000|x∈{0,1}*}。 语言{x000|x∈{0,1}*}与语言{x000y|x,y∈{0,1}*}的不同之处是,前者要求每个 句子都是以000 结尾的,而不是要求句子中含有子串“000”。所以,在构造中,查到3个连续 的0并不表明此串可以被接受,而需要看这3个连续的0是否为输入串的最后3个字符。 因此,通过对图3-3的状态赋予新的解释,并进行适当的修改,以获得接受语言{x000|x∈ {0,1}*}的DFA: 在状态q0 读到的0可能是输入字符串的最后3个0的第一个0。 在状态q1 紧接着读到的0可能是输入字符串的最后3个0的第二个0。 在状态q2 紧接着读到的0可能是输入字符串的最后3个0的第三个0。 在状态q3 紧接着读到的0也可能是输入字符串的最后3个0的第三个0。 如果在状态q1,q3 读到的是1, q2,则要重新检查输入串是否以3个0结尾。 形式语言与自动机理论(第4 版) 所以,相应的DFA 的状态转移图如图3-4所示。 图3-4 接受语言{x000|x∈{0,1}* }的DFA 以下几点值得注意: (1)图3-4清楚地表示出了接受语言{x000|x∈{0,1}* }的DFA,所以,定义FA 时,常 常只给出FA 相应的状态转移图就可以了。 (2)对于DFA 来说,并行的弧按弧上标记字符的个数计算。对于每个顶点来说,它的 出度恰好等于输入字母表中所含字符的个数。 (3)不难看出,字符串x 被FAM 接受的充分必要条件是,在M 的状态转移图中存在 一条从开始状态到某一个终止状态的有向路,该有向路上从第一条边到最后一条边的标记 依次并置构成字符串x。简称此路的标记为x。 (4)一个FA 可以有多于一个的终止状态。例如,图3-5是接受语言{x000|x ∈{0, 1}* }∪{x001|x∈{0,1}* }的FA,它有两个终止状态。 图3-5 接受语言{x000|x∈{0,1}* }∪{x001|x∈{0,1}* }的FA 为了更方便地描述FA 识别一个输入串的过程,定义FA 的即时描述。 定义3-5 设M =(Q,Σ,δ,q0,F)为一个FA,x,y∈Σ*,δ(q0,x)=q,xqy 称为M 的 一个即时描述(instantaneousdescription,ID)。它表示xy 是M 正在处理的一个字符串,x 引导M 从q0 启动并到达状态q,M 的读头当前正指向y 的首字符。 如果xqay 是M 的一个即时描述,且δ(q,a)=p,则 xqay M xapy 表示M 在状态q 时已经处理完x,并且读头正指向输入字符a,此时它读入a 并转入状态 p,将读头向右移动一格,指向y 的首字符。 将M 看作M 的所有即时描述集合上的二元关系,并用nM ,*M ,+M 分别表示M ( )n , M ( )* ,M ( )+ ,按照二元关系合成的意义,有 78 有穷状态自动机 第 n α2,… , Mβ:表示 M 经过 n 次移动,即时描述从 α 变成β。即 M 存在即时描述α1, α 3 章 Mα2,…, 1 Mβ。 αn-1,使得 α α1 αn- Mα1, 0 97 Mα。 当n=0时,有α=β。即 α + Mβ:表示 M 经过至少1次移动,即时描述从 α 变成β。 α α * Mβ:表示 M 经过若干步移动,即时描述从 α 变成β。 当讨论的问题中只有唯一的FA M 时,所进行的移动只能是 M 中的移动,此时符号中 n * 的 M 就可以省略了。一般地,为了简洁起见,当意义清楚时,将符号 M , M , M , + 中的 M 省 M 去,分别用 , n ,*, + 表示 。 例如,用例3-3所定义的 M 处理输入串1010010001, 有 q01010010001 1q0010010001 10q110010001 101q00010001 1010q1010001 10100q210001 101001q00001 1010010q1001 10100100q201 101001000q31 1010010001q0 即 q01010010001101010010001q0 q01010010001 + 1010010001q0 q01010010001 * 1010010001q0 由于 M 在处理完1010010001 后到达状态q0,所以1010010001 不是 M 接受的语言的 句子,虽然 M 在处理该字符串的过程中曾经经过终止状态q3。 不难证明,对于x∈Σ* , + q0x1 x1q0 q0x10 +x10q1 + q0x100 x100q2 08 形式语言与自动机理论(第4版) q0x000 +x000q3 定义36 设 M =(Σ,q0,为一个FA, 能引导FA 从开始状态到达 q 的字符串的集合为 Q,δ,F) 对.q∈Q, x∈Σ*,q0, 对图3-5所给的DFA,有 set(q)={x|δ(x)=q} et(={,= ε 或者 x 以1但不是001 结尾} q0)x| x ∈Σ* xet((s) ={, = q1)x| x ∈Σ* x 0或者 x 以10 结尾} et((s) ={,=00 或者 x 以100 结尾} q2)x| x ∈Σ* et((s) ={,以000 结尾} q3)x| x ∈Σ* x(x) st((s) ={, x 以001 结尾} q4)x| x ∈Σ* 细心观察会发现,上(e) 述5个集合是两两互不相交的,而且这5个集合的并正好就是该DFA 的输入字母表{0,1}的克林闭包。也就是说,这5个集合是{0,1}* 的一个划分。依照这个 划分,可以定义一个等价关系,在同一集合中的字符串满足此等价关系,不在同一集合中的 字符串不满足此等价关系。 一般地,对于任意一个DFAM =(Σ,q0,F), 按照如下方式定义关系RM : Q,δ, 对.x,使得x∈s和y∈t(同时成立。 y∈Σ*,t( xRMy..q∈Q, q) q) 按照这个定义所得到的关系实际上是Σ* 可以将Σ*划 分成不多于 例34|Q|个等价类。进一步的讨论放在后面进行。 m,构造一个DFA,它接受的语言为{0n1m2k|n,k≥1 }。 该语言的句子的特点是:0在最前面,1在中间,2在最后,它们不可以交叉出现,也不上的一个(e) 等价关系。(s) 利用这个关系,(e) 可以颠倒顺序,字符0,1,2的个数均不可少于1。根据此,需要用4个状态 : q0——— M 的启动状态 。 q1——— M 读到至少一个0,并等待读更多的0 。 q2——— M 读到至少一个0后,读到了至少一个1,并等待读更多的1 。 q3——— M 读到至少一个0后跟至少一个1后,接着读到了至少一个2 。 根据上述分析,可以得到如图3-6所示的状态转移图。 图3- 6 接受语言{0n1m2k|m,的DFA 的主体框架 n,k≥1} 显然,图3-6不是要求的DFA 的状态转移图,因为从此图中可以看出相应FA 的输入字母 表至少要包含字符0,1,2,但是图中每个状态处并没有给出所有这3个字符的移动。按照 语言的要求,如果未被标出的字符在这些状态出现,相应的输入串就肯定不是语言的句子。 因此,我们引入第五个状态qt,一旦先前引入的状态发现输入串肯定不是语言的句子,就进 入此状态,完成对输入字符串剩余部分的读入,即进行相应的例外处理。从而得到识别语言 0k≥1} {n1m2k|n,m,的DFA(图37)。 有穷状态自动机 第 3 章 18 图3-接受语言{n1k|m,的DFA 70m2n,k≥1} 本例中有以下几点值得注意: (1)FA 一旦进入状态q它就无法离开此状态。所以, t ta)。 t, q相当于一个陷阱状态(rp 一般地,将陷阱状态用作在其他状态下发现输入串不可能是该FA 所识别的语言的句子时 所进入的状态。在此状态下,FA 读完输入串中剩余的字符。陷阱状态的引入,使得FA 的 构造更方便。 (2)在构造一个识别给定语言的FA 时,用画图的方式比较方便、直观。可以先根据语 言的主要特征画出该FA 的“主体框架”,然后再去考虑一些细节要求。 (3)FA 的状态具有一定的记忆功能,不同的状态对应于不同的情况。由于FA 只有有 穷个状态,所以,在识别一个语言的过程中,如果有无穷种情况需要记忆,肯定是无法构造出 相应的FA 的。例如,对语言{0n1n|n≥1}, 当扫描到 n 个0时,需要去寻找 n 个1,由于 n 有无穷多个,所以,需要记忆的0的个数有无穷多种。因此,无法构造出接受语言{0n1n|n≥1} 的FA 。这就是说,语言{0n1n|n≥1}不属于FA 可以接受的语言类。相应的证明留到研究 FA 接受的语言类的性质时进行。 例35 构造一个DFA,它接受的语言为{x|x∈{0,1}*,且当把 x 看成二进制数时, x 模3与0同余}。 1字符串。当把它们看成二进制数表示时, 从题目要求来看,该语言的句子都是0,它们就 是二进制数。先不考虑以0开头的非0数问题。作为一个二进制数, x 应该是非空的字符串。 解答此题的第一个想法可能是希望构造的DFAM 在读入字符串的过程中按照二进制的解释 计算出它的值,然后计算出它除以3后的余数,当余数为0时就接受该字符串,否则就不接受。 由于x∈{1}* 所以 x 有无穷多种,要计算出每个 x 的值,就要求 M 能够记忆这些值。但 0,, 是, M 要想记忆这些值,就必须有无穷多个状态,每个状态只能对应一个值。所以,这种方法 是不可取的。在定义3-6中曾经提到过,DFAM 按照语言的特点给出了Σ*的一个划分,这种 划分相当于Σ*上的一个等价分类, M 的每个状态实际上对应着相应的等价类。这就告诉我 们,用一个状态去表示一个等价类是考虑问题的一个有效思路。现在的问题是如何确定这些 等价类。题目要求的是 x 模3与0同余,1,——任意一个 x 都 x 除以3的余数只有3种:0,2— 不例外,因此可以考虑用3个状态分别与这3个等价类相联系: q0———对应除以3余数为0的 x 组成的等价类。 q1———对应除以3余数为1的 x 组成的等价类。 q2———对应除以3余数为2的 x 组成的等价类。 此外,由于要求 x 是非空的,所以还需要一个开始状态: 28 形式语言与自动机理论(第4版) qs ——— M 的开始状态。 下面逐一考虑在一个状态下读入一个字符时应该如何改变状态: qs ———读入0时,有x=0,所以应该进入状态q0;读入1时,有x=1,所以应该进入状 态q1。即δ(s,=δ(s,=。 q0)q0,q1)q1 q0———能引导 M 到达此状态的 x 除以3余0,所以有x=3n+0 。 当 M 在此状态下读入0时,引导 M 到达下一个状态的字符串为x0,此时x0= 2(3n+0)=3×2n+0 。这表明,x0应该属于q0 对应的等价类。所以, M 在q0 状态下读入0后,应该继续保持状态q0。即δ(q0,0)=q0。 当 M 在此状态下读入1时,引导 M 到达下一个状态的字符串为x1,此时x1= 2(3n+0)+1=3×2n+1 。这表明, 。即δ(1) M 在 x1应该属于q1 对应的等价类。所以, q0 状态下读入1后,应该转到状态q1 q0,=q1。 q1—— — 能引导 M 到达此状态的 x 除以3余1,所以有x=3n+1 。 当 M 在此状态下读入0时,引导 M 到达下一个状态的字符串为x0,此时x0= 2(3n+1)=3×2n+2 。这表明,x0应该属于q2 对应的等价类。所以, M 在q1 状态下读入0后,应该转到状态q2 q1,=q2。 。即δ(0) 当 M 在此状态下读入1时,引导 M 到达下一个状态的字符串为x1,此时x1= 2(3n+1)+1=3×2n+2+1=3(2x1应该属于q0 对应的等价 n+1 )。这表明, 类。所以, M 在q1 状态下读入1后,。即δ(1)q0 应该转到状态q0 q1,=。 q2—— — 能引导 M 到达此状态的 x 除以3余2,所以有x=3n+2 。 当 M 在此状态下读入0时,引导 M 到达下一个状态的字符串为x0,此时x0= 2(3n+2)=3×2n+43(2n+1)+1 。这表明, q2,=q1 =x0应该属于q1 对应的等价类。 所以, M 在q2 状态下读入0后,应该转到状态q1。即δ(0)。 当 M 在此状态下读入1时,引导 M 到达下一个状态的字符串为x1,此时x1= 2(n+2)+13×2=2n+1)+2 。这表明, 3=n+4+13(x1应该属于q2 对应的等价 类。所以, M 在q2 状态下读入1后,。即δ(1)=q2。 应该继续保持状态q2 q2, 按照上述分析,可以得到所求的DFAM 的状态转移图,如图3-8所示。 图3接受语言{x∈{0,1}* 且当把 x 看成二进制数时,的DFA - 8 x| , x 模3与0同余} 注意, M 所接受的语言中,含有形如000 的0和形如000011 的非0二进制数。这些与 通常的习惯是不一样的。请读者对图3-8所给出的 M 进行修改,使得 M 接受的语言中不 含0n>1)的串和以0开头的非0串。 n ( 有穷状态自动机 例36 构造一个DFA,它接受的语言L={x|x∈{0,1}*,且对 x 中任意一个长度 不大于5的子串a1a2…an ,n≤5 )}。 a1+a2+…+an ≤3( 对{0,1}*中的任意一个字符串a1a2…am ,当 m ≤3 时,肯定是满足要求的。当串的长 度大于或等于4时,必须进行适当的考查,看是否存在不满足要求的子串。如果发现这样的 子串,相应的字符串就一定不是 L 的句子,此时,可以让DFAM 进入“陷阱状态” t,读完输 入串中剩余的字符。为了叙述方便,按照子串的定义及DFA 处理输入串的过程 q———从左 到右逐个扫描输入串中的每个字符,来讨论DFA 的构造。设输入串为 a1a2…ai…ai+4ai+5…am M 对输入串的考查应按下列过程进行: 当i=1,2,3,也就是 M 读到输入串的第1、第2、第3个字符时,它需要将这些字符记下 来。因为a1a2…ai 可能需要用来判定输入串的最初4~5个字符组成的子串是否满足语言 的要求。 当i=4,5,也就是 M 读到输入串的第4,5个字符时,在a1+a2+…+ai≤3 的情况下, M 需要将a1a2…ai 记下来;在a1+a2+…+ai>3 时, M 应该进入陷阱状态qt。 当i=6,也就是 M 读到输入串的第6个字符时,此时,以前读到的第1个字符a1 就没 有用了,它要看a2+a3+…+a6≤3 是否成立,如果成立, M 需要将a2a3…a6 记下来;在 a2+a3+…+a6>3 时, M 应该进入陷阱状态qt。 当i=7,也就是 M 读到输入串的第7个字符,此时,以前读到的第2个字符a2 就没有 用了,它要看a3+a4+…+a7≤3 是否成立,如果成立, M 需要将a3a4…a7 记下来;在a3+ a4+…+a7>3 时, M 应该进入陷阱状态qt。 …… 以此类推,当 M 完成对子串a1a2…ai …ai+4 的考查,并发现它满足语言的要求时, M 记下 来的是aiai+1…ai+4,此时 M 读入输入串的第i+5 个字符ai+5,以前读到的第 i 个字符ai 就没有用了,它要看ai+1+ai+2+…+ai+5≤3 是否成立,如果成立, M 需要将aaai+5 记下来;在ai+1+ai+2+…+ai+5>3 时, M 应该进入陷阱状态qt。 i+1,i+2,…, 从上述分析来看, M 需要记忆的内容有 : 什么都未读入———20=1种 。 记录1个字符———21=2种 。 记录2个字符———22=4种 。 记录3个字符———23=8种 。 记录4个字符———24-1=15 种 。 记录5个字符———25-6=26 种 。 记录当前的输入串不是句子———1种 。 可见 M 需要记忆的内容是有限多种。分别用不同的状态对应要记忆的不同内容。为了便 于理解,直接用要记忆的内容来区分这些状态: q[—— M 还未读入任何字符。 ε] — qt ———陷阱状态 。 q[— M 记录有 i 个字符,a1,ai∈{0, a1a2…ai]——1≤i≤5 。其中,a2,…,1} 。 取DFAM =(Q,{1},q[F) , 0,δ,ε],其中, 38 第 章 形式语言与自动机理论(第4 版) F={q[ε]}∪{q[a1a2…ai]|a1,a2,…,ai∈{0,1}且1≤i≤5且a1+a2+…+ai≤3} Q={qt}∪F δ(q[ε],a1)=q[a1] δ(q[a1],a2)=q[a1a2] δ(q[a1a2],a3)=q[a1a2a3] δ(q[a1a2a3],a)= q[a1a2a3a] 如果a1+a2+a3+a≤3 qt 如果a1+a2+a3+a>3 { δ(q[a1a2a3a4],a)= q[a1a2a3a4a] 如果a1+a2+a3+a4+a≤3 qt 如果a1+a2+a3+a4+a>3 { δ(q[a1a2a3a4a5],a)= q[a2a3a4a5a] 如果a2+a3+a4+a5+a≤3 qt 如果a2+a3+a4+a5+a>3 { δ(qt,a1)=qt 在以上各式中,a,a1,a2,a3,a4,a5∈{0,1}。 在本例中,没有采用状态转移图的表示方法,也没有逐个地写出每一个具体输入字符和 状态的定义,而是以变量(模式)的形式给出的,可以算作新的表示方式。因为本例给出的状 态较多,共计57个,如果逐一给出每一个具体输入字符和状态的定义,会显得比较繁杂,也 不宜理解。建议读者在今后描述FA 时,根据具体的情况使用适当的方式。另外,也请读者 考虑,是否可以去掉那些记录5个字符的状态。 此外,请读者注意,本例中使用的描述方式也可以理解成FA 的状态具有有穷的存储功 能。对本例而言,FA 的状态最多可以存放5个字符。在开始未读入字符时,它的存储器是 空的,然后每读入一个字符,就按照排队的顺序将当前读入的字符存入存储器,直到存储器 中存满5个字符。在存储器中存满5个字符后又读入新的字符,此时将排在队首的字符“挤 掉”,并将当前读入的新的字符放入队尾。 与前面曾给出的FA 相比,本例所给的FA 的状态明显要多很多。在一些实际问题的 求解中,会遇到需要更多状态的FA。本例所给的FA 的状态数是否可以减少呢? 粗略地考 虑,这种可能性是存在的。在处理字符串的过程中,是在考查当前5个字符的和是否不大于 3,这就是说,可以根据和的情况以及1在长度为5的子串中的分布来给出新的状态,而且这 个新的状态有可能代表现在所给FA 的若干状态。很明显,这种状态的设置是比较困难的。 实际上,目前也不用从这样“颇费脑筋”的途径去寻找状态更少的等价FA。后面,将从FA 所接受语言的一般特征出发,给出获取含有最少状态的FA 的方法。 3.3 不确定的有穷状态自动机 3.3.1 作为对DFA 的修改 考虑这样一个问题:设Σ={0,1},现在需要构造一个接受L={x|x∈Σ*,且x 含有子 串00或11}的DFA。按照例3-6所给的构造方法,可以比较容易地构造出如表3-4所示 的DFA。 84 有穷状态自动机 第 表3- 4 接受 L 的DFA 3 章 58 状态说明状态 输入字符 0 1 开始状态q[ε] q[0] q[1] 刚读入的字符为0 q[0] q[00] q[1] 刚读入的字符为1 q[1] q[0] q[11] 含00,终止状态q[00] q[00] q[00] 含11,终止状态q[11] q[11] q[11] 类似地,也可以给出接受语言{x|x∈Σ*,且 x 的倒数第10 个字符为1}的DFA 。在没 有掌握上述方法时,构造会显得非常困难。是否可以考虑图3-9和图3-10 所示的FA 的构 造呢? 如果可以,也就是说,这两个图给出的确实也是FA,那么,今后在构造FA 时就更方 便了。 图3希望是接受语言{*,且 x 含有子串00 或11}的FA - 9 x|x∈{0,1} 图3希望是接受语言{x∈{0,1}*,且 x 的倒数第10 个字符为1}的FA -10 x| 这两个图所给的FA 与前面所定义的DFA 的区别在于: (1)并不是对于所有的(a)∈Q×Σ,q,都有一个状态与之对应。 q,δ(a) (2)并不是对于所有的(a)∈Q×Σ,q,只对应一个状态。 q,δ(a) 在这种FA 中,对于所有的(δ(a)对应的是 Q 的一个子集。对此可 q,a)∈Q×Σ,q, 以理解成:FA 在任意时刻可以处于有穷多个状态,由于 Q 是有穷的,所以,2Q 也是有穷 的。由此可见,这种FA 仍然是具有有穷个状态———它在任意时刻处于的多个状态构成 Q 的一个子集。因此,可以认为这种FA 的一个状态对应的是先前定义的DFA 的一个状 态集合。 实际上,甚至还可以认为,这种FA 具有“智能”:在一个状态下,它可以根据当前从 输入字符串读入的字符自动地在集合δ(q,a)中选择进入一个正确的状态。例如,在 图3-9所示的FA 中,一旦它发现当前读入的0是要寻找的00 中的第一个0(或者当前读 68 形式语言与自动机理论(第4版) 入的1是要寻找的11 中的第一个1), 它就进入与当前状态不同的下一个新的状态( q1 或 q2); 否则,它一直保持在开始状态(q0)。在图3-10 所示的FA 中,一旦它发现当前读入 的1是倒数第10 个字符,它就进入与当前状态不同的下一个状态(否则, 始状态()。 q1); 就停留在开 q0 在这种前提下,只要在如图3-9和图3-10 所示的FA 中存在一条从开始状态出发,最 终到达某一个终止状态的标记为 x 的路径,那么就认为它接受了串x;否则,认为它不接受 串x。 按照上述分析,这种FA 可以看成对DFA 的扩充,而且它很可能是与DFA 等价的。下 面将首先给出这种FA 相应的定义,然后证明它与DFA 的等价性。 3.2 NFA 的形式定义 3. 定义37 不确定的有穷状态自动机(non-deterministicfiniteautomaton,NFA) M 是 一个五元组: Σ,q0, 其中,Q,Σ, F 的意义同DFA 。 M =(Q,δ,F) q0, δ———状态转移函数,又称为状态转换函数或者移动函数,δ: Q ×Σ →2Q 。对 .(a)∈Q×Σ,q,=p1,pm } 可以 q,δ(a){p2,…,表示 M 在状态 q 读入字符a, 选择地将状态变成p1,p2,…, 或者pm ,并将读头向右移动一个带方格而指向输 入字符串的下一个字符。 定义3-4(FA 的状态转移图)对NFA 有效。根据实际情况,通过明确相应的表达对象, 定义3-5(FA 的即时描述)也可以使用。 根据上述定义,图3-9和图3-10 表示的都是NFA 。将NFA 的状态转移图与DFA 的 状态转移图进行比较,可以看出,DFA 是NFA 的特例。将图3-9和图3-10 表示的NFA 分 别记为M1 和M2,它们的状态转移函数可以用表3-5和表3-6的形式给出。 表3- 5 NFAM1 的状态转移函数 状态说明状态 输入字符 0 1 开始状态q0 {q0,q1} {q0,q2} q1 {q3} . q2 . {q3} 终止状态q3 {q3} {q3} ^:Q×Σ*a∈Σ,在NFA 中,同样需将 δ 扩充为 δ →2Q 。对任意q∈Q,w∈Σ*,有 (^(ε)={}。 1)δq, q ^(={^(r, (2)δq,wa)p|.r∈δq,w), 使得p∈δ(a)}。 有穷状态自动机 第 表3- 6 NFAM2 的状态转移函数 3 章 78 状态说明状态 输入字符 0 1 开始状态q0 {q0} {q0,q1} q1 {q2} {q2} q2 {q3} {q3} q3 {q4} {q4} q4 {q5} {q5} q5 {q6} {q6} q6 {q7} {q7} q7 {q8} {q8} q8 {q9} {q9} q9 {q10} {q10} 终止状态q10 . . ^ 与DFA 类似,由于 δ 的定义域Q×Σ 是 δ 的定义域Q×Σ*的真子集:Q×Σ.Q×Σ*, 所以,对于任意(a)∈Q×Σ,^ 和 δ 都有相同的值,就不用区分这两个符号了。事 q,如果 δ 实上,对于任意q∈Q,a∈Σ,有 ^(^( a)δε^(ε), r, ε 是单位元素 ={p|.r∈δq,使得p∈δ(a)} 根据定义的第(2)条 ={ qq, }, r,根据定义的第(1)条 δq,=q,a) p|.r∈{使得p∈δ(a)} ={p|p∈δ(a)} q 是 r 的唯一值 q,集合的不同描述 ^。所以,今后用 δ 代替 δ =δ(aδ) ( w ) 因此, 进一步扩充 δ 的 由于对.(q,w)∈Q×Σ*,q,是一个集合, 为了叙述方便, 定义域,δ:2Q ×Σ*→2Q 。对任意P.Q,w∈Σ*,有 w)δ(w) q∈ P q,, 由于,对.(w)∈Q×Σ* 有 δ(P,=∪ q, δ({w)=q∈{ δ(w) q},∪ q, =δ( q} w) q, 所以,并不一定严格地区分 δ 的第一个分量是一个状态还是一个含有一个元素的集合。这 样,对任意q∈Q,a∈Σ, δ(wa)δ(q,a) w∈Σ*,有 q,=δ(w), 88 形式语言与自动机理论(第4版) 可见,NFAM 从状态 q 出发,处理字符串wa 的过程为: M 先处理w,然后从处理 w 后所 到达的状态出发,处理字符a,并进入处理字符 a 后所能到达的所有状态。即对一个字符串 w,NFAM 与DFA 类似,从左到右逐一地处理每个字符,它从处理完字符串中的第 i 个字 符后所进入的状态集合中的任意状态开始,处理字符串中的第i+1 个字符。也就是说,对 输入字符串a1a2…an ,有 n )δ((…δ(q,a1),a2),…), n ) δ(q,a1a2…a=δ( a 定义38 设 M =(是一个NFA 。对于.x∈Σ*,如果δ( Q,Σ,δ,q0,F) q0,x)∩ F≠., q0,x)∩F=., 则称 x 被 M 接受;如果δ( 且δ( 则称 M 不接受x。 L( M )={x|x∈Σ* q0,x)∩F≠.} 称为由 M 接受(识别)的语言。 关于FA 的等价定义3-3也适应NFA 。 NFA 和DFA 是什么关系? 我们希望从识别L={x|x∈{0,1}*且 x 的倒数第3个字 符是 例371}的NFA 和DFA 的构造得到启发。 构造识别L={x|x∈{0,1}*且 x 的倒数第3个字符是1}的NFA 和DFA 。 图3-10 给出了{x|x∈{0,1}*且 x 的倒数第10 个字符是1}的NFA,参照图3-10,很 容易得到图3-11 所示识别 L 的NFA 的状态转移图。我们将此NFA 记作M1。 图3识别L={*且 x 的倒数第3个字符是1}的NFAM1 的状态转移图 -11 x|x∈{0,1} 为了构造出识别该语言的DFA,一种策略是按照如下思路进行构造。构造的结果如 图3-12 所示。不妨将此DFA 记作M2。 考虑到要识别的是倒数第3个字符是1的0、1串,利用状态的有穷记忆功能记录可能 是输入串的倒数第3个字符“1”及相关信息。不难看出,状态最多只需要存放当前最新读入 的3个字符。 为了表达清晰和简洁起见,这里使用一个新的命名规则:直接用当前存储器中存放的 内容作为状态名称,从而有形如[ab的状态, b,0,为最新读 ε] ε]、[a]、[b]、[ac] 其中a,c∈{ 11} 入的字符,[对应开始“记录”当前字符是否可能为输入串的倒数第3个字符“的(”) 状态,也 就是启动状态。 ε] 如果读到的是0, 从启动状态[开始, 则它肯定不是要找的输入串的倒数第3个字符 ,(”) 停留在状态[ “1因此, ε]; 如果读到的是1,则它有可能是要找的输入串的倒数第3个字符 “1,(”) 需要将这个1记录下来,因此进入状态[1]。从而有 δ([ε],0)=[ ε] δ([1)=[1] ε], 在状态[1], 如果读到的字符是0,表明到目前为止,读到的倒数第2和倒数第1个字符 依次是1和0,而它们都可能是该输入串的倒数第3个字符,虽然0肯定不是要找的倒数第 3个字符“1”,但它需要用来表明它前面的1是目前的倒数第2个字符,所以需要记录下来, 有穷状态自动机 第 因此进入状态[10]; 如果读入的字符是1,表明到目前为止,读到的倒数第2个字符和倒数 3 第1个字符都是1,而它们都有可能是要找的输入串的倒数第3个字符“1,(”) 都需要记录下 章 来,因此进入状态[11 ]。从而有 δ([1],0)=[10] 98 δ([1],1)=[11] 在状态[10], 如果读到的字符是0,表明到目前为止,读到的倒数第3个字符、倒数第2 个字符和倒数第1个字符依次是1,0,0,而它们都很可能是输入串的倒数第3个字符,而且 这两个0都需要用来表明它们前面的这个1目前是倒数第3个字符,所以,新读入的0也需 要记录下来,因此进入状态[100]; 如果读入的字符是1,表明到目前为止,读到的倒数第3 个字符、倒数第2个字符和倒数第1个字符依次是1,0,1,这两个1都有可能是要找的输入 串的倒数第3个字符“1”。中间的0需要用来表明它前面的1的位置,所以,都需要记下来, 因此进入状态[101 ]。从而有 δ([10],0)=[100] δ([10],1)=[101] 在状态[11], 如果读到的字符是0,表明到目前为止,读到的倒数第3个字符、倒数第2 个字符和倒数第1个字符依次是1,1,0,这两个1都有可能是要找的输入串的倒数第3个 字符“1,(”) 虽然新读入的0不可能是倒数第3个字符“1,(”) 它同样需要记录下来,用于体现 [11]中的两个1的位置,因此进入状态[110]; 如果读入的字符是1,表明到目前为止,读到 的倒数第3个字符、倒数第2个字符和倒数第1个字符依次是1,1,1,而它们都有可能是要 找的输入串的倒数第3个字符“1”,都需要记下来,因此进入状态[111 ]。从而有 δ([11],0)=[110] δ([11],1)=[111] 在状态[100], 再读入一个新的字符,无论这个字符是0还是1,都表明状态[100]所记 录的第一个字符1肯定不是倒数第3个字符,不用再保留。如果读到的字符是0,而到目前 为止,读到的倒数第3个字符、倒数第2个字符和倒数第1个字符都是0,此时,无论是不是 倒数第3个字符,它们肯定都不是要找的输入串的倒数第3个字符“1,(”) 而且它们都不需要 用来表明某个1的位置,此时需要重新开始寻找输入串的倒数第3个字符“1,(”) 因此回到状 态[ε]; 如果读入的字符是1,表明到目前读到的字符为止,倒数第3个字符、倒数第2个字 符和倒数第1个字符依次是0,0,1,前面的两个0都不可能是输入串的倒数第3个字符 “1,(”) 而且它们对表明当前读入的字符1是不是倒数第3个字符也没有意义,所以不用再存 储,而这里的1则可能是输入串的倒数第3个字符,因此回到状态[1]。从而有 δ([100],=[ 0)ε] δ([100],1)=[1] 在状态[101], 再读入一个新的字符,无论这个字符是0还是1,都表明状态[101]所记 录的第一个字符1肯定不是要找的输入串的倒数第3个字符“1,(”) 所以,无须保留;此时状态 [101]中的0也肯定不是要找的输入串的倒数第3个字符“1而且这个0对表明当前读入 的字符是不是倒数第3个字符也没有意义,所以这个0也不用再保留。状态[101]中的第3 个字符1,仍然可能是要找的输入串的倒数第3个字符“1”,所以需要保留。此时,如果新读 入的字符是0,则当前倒数第2个字符和倒数第1个字符依次是1和0,因此回到状态[10]; ,(”) 09 形式语言与自动机理论(第4版) 如果读入的字符是1,则当前倒数第2个字符和倒数第1个字符都是1,因此回到状态[11 ]。 从而有 δ([101],0)=[10] δ([101],1)=[11] 在状态[110], 再读入一个新的字符,无论这个字符是0还是1,都表明状态[110]所记 录的第一个字符1肯定不是倒数第3个字符,所以无须保留。此时如果新读入的是0,它需 要用来表明状态[110]中10 的位置,所以需要记录下来,因此进入状态[100]; 如果读入的字 符是1,表明目前读到的字符为止,倒数第3个字符和倒数第1个字符都是1,而它们都有可 能是要找的输入串的倒数第3个字符“1,(”) 而其中的0需要用来表示10 中的1的位置,所以 这个0也需要保留下来,因此进入状态[101 ]。从而有 δ([110],=[ 0)100] δ([110],=[ 1)101] 在状态[111], 再读入一个新的字符,无论这个字符是0还是1,都表明状态[111]所记 录的第一个字符1肯定不是倒数第3个字符,所以无须保留。此时如果新读入的是0,它需 要用来表明状态[111]中后两个1的位置,所以需要记录下来,因此进入状态[110]; 如果读 入的字符是1,表明目前读到的字符为止,倒数第3个字符、倒数第2个字符和倒数第1个 字符都是1,而它们都很可能是输入串的倒数第3个字符“1,(”) 因此进入状态[111 ]。从而有 δ([111],=[ 0)110] δ([110],=[ 1)111] 这里的状态[100],[101],[110],[111]都表达了当前已经读入的串的倒数第3个字符 是1,满足 L 的要求,所以它们是终止状态,而其他状态都表达了当前已经读入的串的倒数 第3个字符不是1,不满足 L 的要求,所以这些状态就不是终止状态。 这个DFA 的状态转移图如图3-12 所示,我们将它记作M2。 图3识别L={x∈{0,* 且 x 的倒数第3个字符是1}的DFAM2 的状态转移图 -12 x|1}, 我们回到图3-11,按照NFA 的移动函数 δ 的扩展意义,容易得到如表3-7所示的计算 结果。请读者注意此表中第2列中状态集合的出现顺序,以设计出生成此表的算法,对根据 给定的NFA 构造等价的DFA 具有重要意义。