授课顺序：5
教学目的：让学生掌握DFA和NFA的定义，了解DFA和NFA的表示方法，掌
握NFA与DFA的等价转换方法及DFA的化简方法。
教学重点：DFA和NFA的定义、等价转换及DFA的化简 教学难点：DFA和NFA的等价转换、DFA的化简 授课学时：2学时 教学方式：多媒体讲授 教学内容：
4.3有穷自动机
一、概述
有穷自动机(Finite Automata):可准确识别正规集（即识别正规文法所定义的语言和正规式所表示的集合）的一种装置。它分为两类:
(1)确定的有穷自动机(Deterministic Finite Automata，简称DFA)
(2)不确定的有穷自动机(Nondeterministic Finite Automata，简称NFA)
二、确定的有穷自动机(DFA) 1、定义
确定的有穷自动机表示为一个五元组：M=(K，?，f，S，Z)，其中：
(1) K是一有穷状态集；
(2)?是一有穷字母表，称输入符号字母表；
(3) f是转换函数，是在K??→K上的映射。如f(ki，a)=kj； (4) S是唯一的一个初态；
(5) Z?K，是一终态集，终态也称结束态或可接受态。
2、DFA的状态图表示
假设DFA M有m个状态，n个输入字符，则：
(1)状态图有m个结点，每个结点最多有n条弧射出； (2)有唯一的一个初态结点，前面冠以“=>”或“-”标记； (3)有若干终态结点，用双圆圈或“+”标记；
例：下图所示DFA可识别正则集L(ab*c)，如串abbc可被认别。
3、DFA的矩阵表示 (1)行表示状态；
(2)列表示输入字符则；
(3)矩阵元素表示相应状态行和输入字符列下新状态（即k行a列为f(k，a)的值）； (4)用“=>”标记行或第一行表示初态；
(5)终态行右端标以1，非终态行右端标以0。 例：上图也可表示为矩阵形式：
a b c
S A 0
A A B 0 B 1 4、转换函数定义扩充
方便起见，对DFA中转换函数定义进行扩充：f是转换函数，是在K??*→K上的映
射，有：
(1) f(k1，ε)=k1
(2) f(k1，aα)=f(f(k1，a)，α) 其中，k1∈K，a∈? ，α∈?*。 5、接受(识别)
设DFA=(K，?，f，S，Z)，若f(S，α)=P∈Z，则称符号串α∈?*可被该DFA接受(识别)。
例:试证串abbc可被图示DFA识别。
证：f(S，abbc)=f(f(S，a)，bbc)=f(f(A，b)，bc) =f(f(A，b)，c)=f(A，c)=B 由于B为终态，得证。 6、语言
确定有穷自动机M所接受的所有符号串集称为此自动机可接受的语言L(M)。 7、重要结论
(1)?上的一个字符串集V??*是正规集，当且仅当存在着一个?上的确定有穷自动机M，使得V=L(M)。
(2) DFA的确定性表现在状态转换函数是单值函数，即f(k，a)唯一确定一个后继状态。
二、不确定的有穷自动机(NFA) 1、定义
不确定的有穷自动机表示为一个五元组：NFA M=(K，?，f，S，Z)，其中：
(1) K是一有穷状态集
(1)?是一有穷字母表，称输入符号字母表
(3) f是转换函数，是在K??*→K的子集上的映射。 (4)S是初态集
(5) Z?K，是一终态集，终态也称结束态或可接受态。
例：状态图表示的NFA如下：
状态图表示的DFA如下：
4、转换函数定义扩充
因为f是转换函数，是在K??*→K的子集上的映射，有： (1) f(k，aα)=f(k1，α)∪f(k2，α)...∪f(kn，α)
其中，ki∈K，a∈? ，α∈?*，且f(k，a)={k1，k2，....kn} 5、接受(识别)
设NFA=(K，?，f，S，Z)，如果z0∈f(S，α)且z0∈Z，则称符号串α∈?*可被该NFA接受(识别)。
例:试证串abc可被图示NFA识别。
证：f(S，abc)=f(A，bc)=f(A，c)∪f(C，c)=B，又因为B∈ 终态集{B}，得证。 6、语言
不确定有穷自动机M所接受的所有符号串集称为此自动机可接受的语言L(M)。 7、重要结论
(1）对于每个NFA M，必存在一个DFA M1，使得L(M)=L(M1)；
(2)对于任何两个有穷自动机M1和M2，若L(M1)=L(M2)，则称有穷自动机M1和M2等价。
三、ＮFA到DFA的转换 1、相关概念
ε闭包：ε-closure(I)表示状态集I中任何状态A经任意条ε弧而能到达的状态集。 状态集I的a弧转换：表示为J=move(I，a)，J是所有那些从I中任一状态经一条a弧而到达的后继状态全体。
令:Ia=ε-closure(J)=ε-closure(move(I，a))
例：对下图NFA，取I={S，1}，则ε-closure(I)＝{S，1，2}，J=move(I，0)={1}， I0=ε-closure(J)={1，2}
2、NFA的确定化
用造表法将NFA确定化过程如下： (0)表的第0行和第0列作标识行列的值。 (1)将ε-closure(I)作为表中第1行第1列。
(1)假定?={a1，a2，...an}，设第i行第一列已确定状态集为I，则置该行第i列为Iai，如Iai未曾在任何行第一列出现过，则将Iai加入下一空行i+1的第一列，并在第0列标记为Ti+1。
(3)反复重复第(1)步，直至无新状态出现为止。 (4)重新命名新状态。
例：将上图所示NFA确定化(0-3步：造表)
整理后得： 重新命名新状态得DFA如下图所示：
四、DFA的化简 1、相关概念
(1)一个DFA是化简(最小化)了的，即它没有多余状态且其状态中没有相互等价的。 (2)多余状态是指从自动机的开始状态出发，任何输入串也不可达的状态。 2、状态等价
在DFA中，两个状态s和t等价的条件是：
(1)一致性条件：状态s和t必须同时为可接受态和不可接受态。
(2)蔓延性条件：对于所有输入符号，状态s和t必须转换到等价的状态里。 3、DFA最小化处理
对DFA最小化的本质：消除多余状态、合并等价状态。
DFA最小化具体过程：用分割法将不含多余状态的DFA分成一些不相交的子集，使得任何两个不同的子集中的状态都是可区别的，而相同子集中状态是等价的。分割时，首先将DFA状态分成终态子集和非终态子集，再根据输出弧所达到状态的性质逐步细分。 例：对左图所示DFA最小化。
解：P0={{1，2，3}，{4，5，6，7}}
根据各子集输出弧0和1所达到状态是否为终态，划分为：P1={{1}， {2}， {3}，{4，5，6，7}}，最小化后DFA如上右图所示。