第六章
有限状态自动机和有限状态语言
? 已经介绍过从产生语言的角度定义语言的
形式；下面从识别语言的角度来定义语言。
? 有限状态自动机 (FSM,finite state
machine”或者 FSA,finite state
automaton”)是为研究有限内存的计算过
程和某些语言类而抽象出的一种计算模型。
? 有限状态自动机拥有有限数量的状态，每
个状态可以迁移到零个或多个状态，输入
字串决定执行哪个状态的迁移。有限状态
自动机可以表示为一个有向图 (称之为状
态转换图 )。
? 有限状态自动机是自动机理论的研究对象。
? 有多种类型的有限状态自动机：接受器判
断是否接受输入；转换器对给定输入产生
一个输出。常见的转换器有 Moore机与
Mealy机。 Moore 机对每一个状态都附加
有输出动作,Mealy 机对每一个转移都附
加有输出动作。
? 有限状态自动机还可以分成确定与非确定
两种。非确定有限状态自动机可以转化为
确定有限状态自动机。
? 有限状态自动机识别的语言是正则语言
RL。
? 有限状态自动机除了它在理论上的价值，
还在数字电路设计、词法分析、文本编辑
器程序等领域得到了应用。
6.1 有限状态自动机
? 有穷状态自动机是具有离散输入和输出的系统的
一种数学模型。其主要特点有以下几个方面：
? (1)系统具有有穷个状态，不同的状态代表不同的
意义。按照实际的需要，系统可以在不同的状态
下完成规定的任务。
? (2)我们可以将输入字符串中出现的字符汇集在一
起构成一个字母表。系统处理的所有字符串都是
这个字母表上的字符串。
? (3)系统在任何一个状态下，从输入字符串中读
入一个字符，根据当前状态和读入的这个字符
转到新的状态。
? (4)系统中有一个状态，它是系统的开始状态。
? (5)系统中还有一些状态表示它到目前为止所读
入的字符构成的字符串是语言的一个句子
? 有限状态自动机物理模型如图 6-1所示。
? 一个输入存储带，带被分解为单元，每个单元
存放一个输入符号（字母表上的符号），整个
输入串从带的左端点开始存放，而带的右端可
以无限扩充；
? 一个有穷状态控制器（ FSC），该控制器的状
态只能是有穷多个； FSC通过一个读头和带上
单元发生耦合，可以读出当前带上单元的字符。
初始时，读头对应带的最左单元，每读出一个
字符，读头向右移动一个单元（读头不允许向
左移动）。
? 有限状态自动机的一个动作为：
? 读头读出带上当前单元的字符； FSC根据
当前 FSC的状态和读出的字符，改变 FSC
的状态；并将读头向右移动一个单元。
? 有限状态自动机的动作简化为：
? FSC根据当前的状态和当前带上的字符，
进行 FSC状态的改变。
定义 6-1 有限（有穷）状态自动机（接收机）
的定义
? 字母表 ∑上的有限状态接收机（ FSAM）是
一个五元式,FSAM=（ Q,∑,δ,q0,F），
? 其中：
? Q是一个有限状态的集合；
? ∑是字母表，也就是输入带上的字符的集合；
? q0∈ Q是开始状态；
? FСQ是接收状态（终止状态）集合；
? δ是 Q× ∑→Q 的状态转换函数，即 δ(q，
x)= q′；代表自动机在状态 q时，扫描字符
x后到达状态 q′。
? 理论上，有限状态自动机的状态转换函数
的个数应该为 |Q|*|∑|。因为对于 Q中的每
个状态，都应该定义扫描字母表 ∑上的每
个字母的状态转换函数。
? 例 6-2 有限状态自动机 FSAM=（ { q0,q1}，
{0,1},δ,q0,{q0}），其中 δ为：
? 表示为函数形式：
? δ(q0,0)=q1； δ(q0,1)=q1；
? δ(q1,0)= q1； δ(q1,1)= q0；
? 或者表示为状态矩阵的形式。如图 6-2所
示。
? Q 0 1
? q0 q1 q1
? q1 q1 q0
?
? 或者表示为状态图的形式。如图 6-3所示。
? 状态图是一个有向、有循环的图。一个节点
表示一个状态；若有 δ(q,x)= q′，则
? 状态 q到状态 q′有一条有向边，并用字母 x作
标记。
? 一个圆圈代表一个状态,’ → ’ 指向的状
态是开始状态，两个圆圈代表的状态是接
收状态；在比较明确的情况下，可以用状
态图表示一个有限状态自动机，而有向边
的数目就是状态转换函数的个数。
6.2 有限状态自动机识别语言
? 定义 6-3 有限状态自动机接收串的定义
? 对于有限状态自动机 M,给定字母表 ∑ 上
的串 w=w1w2… wn；初始时, 自动机 M处于开
始状态 q0；从左到右逐个字符地扫描串 w；
在 δ (q0,w1)= q1的作用下, 自动机 M处于
状态 q1,在 δ (q1,w2)=q2的的作用下, 自
动机 M处于状态 q2,… ；
? 当将串 w扫描结束后, 若自动机处于某一
个接收状态, 则称有限状态自动机能够接
收 （ 识别 ） 串 w。 对于自动机而言, 从开
始状态开始, 在扫描串的过程中, 状态逐
个地变化, 直到某个接收状态, 我们把状
态的变化过程称为自动机的一条路径, 而
这条路径上所标记的字符的连接, 就是自
动机所识别的串 。
?定义 6-4 有限状态自动机接收的语言
的定义
?对于字母表 ∑ 上的有限状态自动机 M，
它能识别的所有串的集合, 称为自动
机 M能识别的语言 。 记为 L(M)。
?定义 6-5 扩展的状态转换函数的定义
?给定 FSAM,定义扩展的状态转换函数
δ *,Q× ∑ *→Q 为,δ *（ q,w） =q′
?即自动机在一个状态 q时, 扫描串 w后
到达唯一确定的状态 q′ 。
?定义 6-6 扩展的状态转换函数的形式
定义
?δ *（ q,ε ） =q；
?δ *（ q,x） =δ （ q,x） ；其中 x
是一个字母；
?对于串 w=α x（ x是一个字母, α 是一
个字符串 ） ；
?δ *（ q,w）
?=δ *（ q,α x）
?=δ （ δ *（ q,α ）, x） ；
?或者：对于串 w= xα （ x是一个字母,
α 是一个字符串 ） ；
?δ *（ q,w）
?=δ *（ q,xα ）
?=δ *（ δ （ q,x）, α ）
?定义 6-7 FSAM接收的语言的定义
?L(M)表示被 FSAM=（ Q,∑, δ, q0，
F） 接收的语言, 它在字母表 ∑ 上,
即 L(M） С ∑ *,则
? L(M） ={w|w∈∑ *且 δ *（ q0,w）
∈ F}。
?若语言 LС ∑ *,对于某个有限状态自
动机 M,有 L=L(M),则称语言 L为一个
有限状态语言 （ FSL） 。
定义 6-8 有限状态自动机的瞬
时描述（格局）的定义
?瞬时描述是一个二元式,qy； y∈∑ *，
?其中：
?y是输入带上还没有被扫描到的字符
串, FSC当前状态为 q,读头将马上扫
描 y串的最左边第 1个符号 。
? 格局可以发生转换 （ 改变 ）, 格局发生转
换的原因是由于 δ 函数的一次作用 。
? 如果当前格局为,qar,有 δ 函数,δ (q，
a)= q′, 则下一格局为,q′ r ；
? 格局的转换可以记为,qar => q′ r；
?有限状态自动机初始格局为,q0w；
? 接收格局为,qα ε
?其中,
?q0是开始状态,qα 是某个接收状态；
?使用 =>*代表格局的多次转换 。
?也可以使用格局的转换方式定义有限
状态自动机接收的语言 。
?有限状态自动机接收的语言 L(M)={w|
q0w =>* qα ε ； w∈∑ *且 qα ∈F} 。
? 定义 6-9 有限状态自动机停机的定义
? 有限状态自动机在下面两种情况下停机：
? （ 1） 有限状态自动机将输入串扫描结束时, 或
? （ 2） 有限状态自动机的当前格局为,qar,而
有限状态自动机没有对应的 δ 函数的定义, 即
δ (q,a)=？ （ 此时, 一定没有扫描完输入串 ）
注意 1：
?有限状态自动机停机时, 并不一定接
收扫描过的串 （ 已经读入的符号串 ） ；
?有限状态自动机将输入串扫描结束停
机时, 如果有限状态自动机处于某一
个接收状态, 则表示接收整个串；
? 有限状态自动机将输入串扫描结束停机时, 如
果有限状态自动机没有处于任何的接收状态,
则表示不接收整个输入串；
? 有限状态自动机没有扫描完整个输入串就停机,
一定不会接收整个输入串；如果此时有限状态
自动机处于某一个接收状态, 则说明已经扫描
过的串 （ 是整个串的子串, 而不是整个输入串 ）
能够被有限状态自动机接收 。
注意 2:
? 有限状态自动机的某个状态 q,如果对于字母表
上的字母 x没有对应的 δ 函数的定义, 可以省略
掉该 δ 函数；或者定义一个特殊的状态：陷阱
状态 qt。
? 对于陷阱状态, 定义 δ (q,x)=qt。
? 陷阱状态 qt,仅仅有入口边, 没有出口边, 一定
不是开始状态 。
? 此时, δ 函数的个数 = |Q| * |∑| 。
? 定理 6-10 每个 FSL都是一个右线性语言 。
? 证明思路：
? 假设 L是字母表 ∑ 上的有限状态语言, 且
L=L(FSAM）, FSAM=（ Q,∑, δ, q0，
F）, 构造右线性文法 G=（ ∑, Q,q0,P）
（ 将自动机的状态当作是文法的非终结
符 ）, 其中 P为：
?{q→xq ′ |δ （ q,x） =q′ }
U{ q→x| δ （ q,x） ∈ F }
?特别地, 若开始状态也是接收状态,
则有 q0→ ε ；
? 对于串 w=w1w2… wn：
? 自动机 M,则文法有
? δ（ q0,w1） =q1 q0→w 1q1；
? δ（ q1,w2） =q2 q1→w 2q2；
? … …
? δ（ qn-2,wn-1） =qn-1 qn-2→w n-1qn-1
? δ（ qn-1,wn） =qn qn-1→w nqn
? 或 qn-1→w n
? （ qn是接收状态 ）
? 所以
? 对自动机 M,对文法：
? δ*（ q,α） = q′ q=>*αq′
? δ*（ q0,w） ∈ F q0=>*w
? FSL={（ 0,1） 0*1}*,接收该语言的有限状态自
动机
? 构造右线性文法产生该语言：
? q0→ 0q1|1q1|ε
? q1→ 1q0|0q1|1
定理 右线性语言对补运算是封
闭的
? 证明：
? 假设 L1是字母表 ∑ 上的有限状态语言, 且
L1=L(FSAM1),FSAM1=（ Q,∑, δ, q0,F）, 而
FSAM2=（ Q,∑, δ, q0,Q） 接收的语言是右线
性语言 L1的对应的全集 。
? 对 L1 的 补 运 算 得 到 的 语 言 L2=L(FSAM′ ),
FSAM′ =（ Q,∑, δ, q0,Q-F）, 所以 L2也是
FSL语言 （ 右线性语言 ） 。 证毕 。
? 注意：
? 此时的 FSAM1的 δ 函数的个数 = |Q| * |∑| ；即
需要陷阱状态 。
?
6.3 有限状态自动机识别语言的例子
? 例 6-12 接收语言 L={ab}的有限状态自动机
思考
? 如果将该自动机的所有状态都设置为接收
状态 （ 包括陷阱状态 ）, 那么, 自动机接
收的语言是什么？
? 如果将该自动机的接收状态和非接收
状态对调, 即将状态 S,M,和陷阱状态 qt
都设置为接收状态, 而将原来的接收状态
F设置为非接收状态, 那么, 自动机接收
的语言是什么？
? 构造有限状态自动机 M,识别 {0,1}上的
语言 L={x000y|x,y∈{ 0,1}*}。
? 分析：
? 语言 L={x000y|x,y∈{ 0∈ 0∈{ 0,1}*}，
该语言的特点是语言中的每个串都包含连
续的 3个 0（ 即每个串都包含子串 000）,
? 因此, 对于任何输入串, 有限状态自动机
的任务就是要检查该输入串中是否存在子
串 000,一旦发现输入串包含有 000,则表
示输入串是个合法的句子 （ 是属于语言中
的一个串 ）, 因此, 在确认输入串包含
000后, 就可以逐一地读入输入串的后面
的字符, 并接收该输入串 。
?问题的关键是如何发现子串 000。
?由于字符是逐一读入的, 当从输入串
中读入一个 0时, 它就有可能是 000子
串的第 1个 0,就需要记住这个 0；如
果紧接着读入的是字符 1,则刚才读
入的 0就不是子串 000的第 1个 0,此时,
需要重新寻找 000子串的第 1个 0；
?如果紧接着读入的还是字符 0,它就
有可能是 000子串的第 2个 0,也就需
要记住这个 0,继续读入字符, 如果
还是 0,则表明已经发现子串 000,否
则, 需要重新寻找子串 000。
FSC的状态极其意义
? q0,有限状态自动机的开始状态；也是重新寻找
子串 000时的状态
? q1,有限状态自动机读到第 1个 0,有可能是子
串 000的第 1个 0；；
? q2,有限状态自动机在 q1后又读到 1个 0（ 读到连
续的 2个 0） ；
? q3,有限状态自动机在 q2后又读到 1个 0（ 读到连
续的 3个 0） ； 惟一的接收状态 。
?因此, 基本的状态转移函数为：
? δ (q0,0)=q1
? δ (q1,0)=q2
? δ (q2,0)=q3
?其他状态转移函数为：
? δ (q0,1)=q0
? δ (q1,1)=q0
? δ (q2,1)=q0
? δ (q3,0)=q3
? δ (q3,1)=q3
? 构造有限状态自动机 M, 识别 {0, 1}上的语言
L={x001y|x,y∈{ 0,1}*}。
? 分析：
? 语言 L={x001y|x,y∈{0∈0∈{0, 1}*}，该语言的特点
是语言中每个串都包含子串 001，因此，对于任何输入
串，有限状态自动机的任务就是要检查该输入串中是否
存在子串 001，一旦发现输入串包含有 001，则表示输入
串是个合法的句子（是属于语言中的一个串），因此，
在确认输入串包含 001后，就可以逐一地读入输入串的
后面的字符，并接收该输入串。
? 构造有限状态自动机 M，识别 {0,1}上的语言
L={x000|x∈{0, 1}*}
? 构造有限状态自动机 M，识别 {0,1}上的语言
L={x000}U{x001}，其中 x∈{0, 1}*。
? 构造有限状态自动机 M，识别 {0,1}上的语言
L={02k+3m|m,k>=0}。
? 实际上：
2k+3m可以表示任意的非负整数（除 1外）
? 思考：
? 构造有限状态自动机 M,识别 {0,1}上的语言
L={02k+3m|m,k>0}。
?构造有限状态自动机 M，识别 {0,1}
上的语言，该语言的每个字符串以 0
开头，以 1结尾。
?构造有限状态自动机 M，识别 {0,1}
上的语言，该语言的每个字符串不包
含 00子串（语言允许 ε ）。
?思考：
? 若 语言不允许 ε 。
? 构造有限状态自动机 M，识别 {0,1,2}上
的语言，该语言的每个字符串代表的数字
能整除 3。
? 分析：
? 如果一个十进制整数的所有位的数字的和
能够整除 3,那么, 这个十进制整数本身
就能够整除 3；
? 一个十进制整数除以 3,余数只能是 1,2
和 0（ 余数为 0,则表示该数能够整除 3） ；
? 将整数当作一个字符串, 从左到右逐一地读入；
? 使用 3个状态分别代表已经读入的数字的和除以
3的不同的余数的情况：
? q0：已经读入的数字的和除以 3，余数为 0；
? q1：已经读入的数字的和除以 3，余数为 1；
? q2：已经读入的数字的和除以 3，余数为 2；
?
? 则扫描子串 w后, 处于某个状态, 读入当前数字,
有限自动机的状态转换情况为：
? q0：
? 在此状态读入 0,引导自动机到达下一状态的输
入串为 w0，,w0的各位数字和除以 3,余数为 0。
所以, 自动机在 q0状态读入 0,应该继续保持 q0
状态；
?
? 在此状态读入 1,引导自动机到达下一状态的输
入串为 w1,w1的各位数字和除以 3,余数为 1。
所以, 自动机在 q0状态读入 1,应该到达 q1状态；
? 在此状态读入 2，引导自动机到达下一状态
的输入串为 w2,w2的各位数字和除以 3，余数为
2。所以，自动机在 q0状态读入 2，应该到达 q2状
态；
? …
?对于状态转换图，有一些基本的等价
替换 (参看教材）。
定义 set(q)
?有限状态自动机 FSAM=（ Q,∑, δ,
q0,F）, 对于状态 q,q∈Q ；能将
有限状态自动机从开始状态转换到 q
状态的所有字符串的集合为：
?set(q)={w|w∈∑ *,δ (q0,w)=q}
?则 有限状态自动机 FSAM接收的 语言可
以定义为：
L（ M） =Uset(q)
其中,q∈F
? 一般地, 对于任意一个有限状态自动机
FSAM=（ Q,∑, δ, q0,F）, 可以定义
关系 R,若 x,y∈∑ *, 则 xRy当且仅当
x∈set(q) 且 y∈set(q), 其中,q∈Q 。
? 该关系是集合 ∑ *上的一个等价关系, 利
用该关系, 可以将 ∑ *划分为不多于 |Q|个
的等价类 。
?有限状态自动机可以按照语言的特点
给出字母表 ∑ *的一个划分, 这种划
分相当于 ∑ *上的一个等价分类, 有
限状态自动机的每个状态实际上对应
着一个等价类 。 所以, 利用一个状态
去表示一个等价类是考虑问题 （ 构造
有限状态自动机 ） 的一条有效思路 。
?例构造有限状态自动机 M，识别 {0,1，
2,4,5,6,7,8,9}上的语言，该
语言的每个字符串代表的数字能整除
3。
? 仍然只使用 3个状态分别代表已经读入的
数字的和除以 3的不同的余数的情况：
? q0：已经读入的数字的和除以 3，余数为 0
的输入串的等价类；
? q1：已经读入的数字的和除以 3，余数为 1
的输入串的等价类；
? q2：已经读入的数字的和除以 3，余数为 2
的输入串的等价类；
?构造有限状态自动机 M，识别 {0,1}
上的语言，该语言的每个字符串挡成
二进制数时，代表的数字能整除 3。
? 可能的一个想法是希望构造出的有限状态
自动机在读入 0,1串 （ 二进制串 ） 的过程
中, 按照二进制的解释, 计算出它对应的
十进制数, 再判断是否能整除 3,由于二
进制串有无穷多个, 要计算出每个二进制
串的 （ 十进制 ） 值, 也就需要无穷多个状
态；这种想法是不可取的 。
?有限状态自动机的每个状态实际上对
应着一个等价类 。 所以, 利用一个状
态去表示一个等价类；除以 3的余数
只能为 0,1和 2,使用 3个状态分别代
表已经读入的数除以 3的不同的余数
的等价类：
?q0：已经读入的数除以 3，余数为 0的
输入串的等价类；
?q1：已经读入的数除以 3，余数为 1的
输入串的等价类；
?q2：已经读入的数除以 3，余数为 2的
输入串的等价类；
?因为不能接收空串, 所以, 还需要一
个开始状态 qS。 …
?构造有限状态自动机 M,识别 {0,1}
上的语言 L={0n1m2k|n,m,k>=1}。
?该语言的串的特点是, 0在最前面, 1
在中间, 2在最后, 0,1和 2不能交叉,
顺序也不能颠倒, 并且 0,1和 2的个
数都至少为 1个；需要 4个状态：
? q0：开始状态，等待接收第 1个 0；
? q1：已经读入第 1个 0，等待接收更多的 0；
? q2：已经读入至少 1个 0，且已经接收第 1
个 1，并等待接收更多的 1；
? q3：已经读入至少 1个 0后至少有 1个 1，接
着至少读到 1个 2，并能接收多个 2；
? 构造有限状态自动机 M，识别 {1,2,3}上的语言，
该语言的每个字符串挡成十进制数时，代表的
数字能整除 4 。
? 构造有限状态自动机 M，识别 {0,1,2,3,4,5，
6,7,8,9}上的语言，该语言的每个字符串挡
成十进制数时，代表的数字能整除 4 。
? …
?构造有限状态自动机 FSAM，识别
X={x1,x2,x3,… xM}上的语言，该语
言的每个字符串挡成二进制数
(base=2)或八进制数 (base=8)或十进
制数 (base=10)时，代表的数字能整
除 N。
? 分析：
? 将不同进制的数转换为十进制数后, 除以
N的余数只能为 0,1,2,3… 和 N-1,使用
N个状态分别代表已经读入的数字的和除
以 N的不同的余数的等价类：
? q0：已经读入的数除以 N，余数为 0的输入
串的等价类；该类数为 N*n+0;
? q1：已经读入的数除以 N，余数为 1的输入
串的等价类；该类数为 N*n+1;
? q2：已经读入的数除以 N，余数为 2的输入
串的等价类；该类数为 N*n+2;
? …
? qN-1：已经读入的数除以 N，余数为 N-1的
输入串的等价类；该类数为 N*n+N-1;
?
?注意：因为不能接收空串, 所以, 还
需要一个开始状态 qS。
?qS：在开始状态读入 x时, 进入对应
状态 qx；
?qi：对应已经读入的数 w除以 N,余数为 i
的输入串的等价类；该类数为 N*n+i;
? 当前读入的字符为 x；则 wx表示的十进制
数为：
? base*（ N*n+i） +x
? =N*base*n+base*i+x
?该数对于 N取余数就是 base*i+x对于 N
的余数，若该余数为 j，则相应的状
态就应该从 qi变换为 qj。
?其中：
i=0,1,2,…, N-1。
x为字母 (0~base-1)。
6.4 不确定的有限状态自动机
?每个 FSL都是一个右线性语言, 那么
一个右线性语言是不是一个 FSL呢？
考虑下面的例子：
?接收语言 {aa,ab}的有限状态自动机
? 该自动机识别的语言 L={aa,ab}是一个右
线性语言；但 M不是有限状态自动机,
? 因为,δ （ S,a） = {Q1,Q2},即 δ （ S，
a） 没有到达一个确定的状态 。
? 称这种自动机为不确定的有限状态自动机 。
? FSAM称为确定的有限状态自动机。
6.4.1不确定的有限状态自动机
? 不确定的有限状态自动机 (NDAM)的定义
? NDAM是一个五元式,
NDAM=（ Q,∑,δ,Q0,F）,
? 其中：
? Q是一个有限状态的集合；
? ∑是字母表；
? Q0СQ是开始状态集合；
? FСQ是接收状态 （ 终止状态 ） 集合；
? δ是 Q× ∑→ 2Q的状态转换函数 （ 2Q是指 Q
的幂集 ）, 即 δ(q,x) С2Q ；代表自动机
在状态 q时, 扫描字符 x后到达可能的下一
状态集合 。
? 不确定的有限状态自动机有一个可能的开
始状态集合和可能的下一个状态集合, 其
余的同确定的有限状态自动机 。
? 非确定有限状态自动机与确定有限状态自
动机的唯一区别是它们的转移函数不同 。
确定有限状态自动机对每一个可能的输入
只有一个状态的转移 。 非确定有限状态自
动机对每一个可能的输入可以有多个状态
转移, 接受到输入时从这多个状态转移中
非确定地选择一个 。
? 对于 非确定有限状态自动机,并不是对于
所有的 (q,x)∈ Q× ∑,δ(q,x)都有一个
状态与之对应；并不是对于所有的 (q,x)
∈ Q× ∑,δ(q,a)都只对应一个状态。 δ(q，
x)对应的是状态的一个子集，当这个子集
为空时，表示没有状态与之对应；当这个
子集的元素个数大于 1时，表示有多个状
态与之对应。
?从这个意义上,δ(q,x)仍是通常意
义下的一个函数，只是其值域发生了
改变。当 δ(q,x)对应的所有子集元
素个数为 1时,NDAM退化为 FSAM。
?因此, 在扫描一个串 w时, 经过 NDA
可能会有多条路径, 某些可能会在接
收状态时终止, 某些可能会在非接收
状态时终止；若至少存在一条路径可
以使自动机在扫描串 w后到达接收状
态, 则称串 w能被自动机 NDAM所识
别 。
?对于字母表 ∑上的不确定的有限状态
自动机 M,它能识别的所有串的集合,
称为自动机 NDAM能识别的语言 。 记
为 L(NDAM)。
? 不确定的有限状态自动机扩展状态转换函
数的定义
? 给定 NDAM,定义扩展的状态转换函数 δ*：
2Q× ∑*→ 2Q为
? δ*（ p,w） = Q′,即自动机在状态集合 p
时, 扫描串 w后到达可能的的状态集合 Q′。
? 若 p={ q1,q2,… qn}；
? δ*（ p,ε） =p；
? δ*(p,x)=U{δ（ q,x） |q∈ p； x∈ ∑}；
? ={δ(q1,x),δ(q2,x),…,δ(qn,x)}
? δ*（ p,w） =δ*（ p,xα）
? =U{δ*（ q,α） | q∈ δ*（ p,x） }；
?L(NDAM)表示被不确定的有限状态自
动机 NDAM=（ Q,∑,δ,Q0,F）
所接收的语言, 它在字母表 ∑上, 即
L(NDAM)С∑*,则
?L(NDAM)={w|w∈ ∑*且 δ*（ Q0,w）
∩F!=Φ}。
?它表示输入串 w的集合；在 NDAM的
状态图中, 至少存在一条路径, 以 w
为标记, 能使 NDAM从某个开始状态
到达某个接收状态 。
? 6.4.2不确定的有限状态自动机转换为确定
的有限状态自动机
? 定理 6-31
? ∑*的一个子集 L是一个有限状态语言
（ FSL）, 当且仅当存在 NDAM,使得
? L(NDAM)=L。
证明,=>：
? 若 L是 FSL,则有 FSAM=（ Q,∑,δ,q0，
F）, 且 L=L(M）, 构造
? NDAM=（ Q,∑,δ1,{q0},F）,
? 且 δ1,Q× ∑→ 2Q为：
? δ1（ q,x） ={δ（ q,x） }，
? 即把 FSAM的一个状态当作是 NDAM的一
个状态集合,
? 则 L=L(M） =L(NDAM)。
<=：
?NDAM=（ Q,∑,δ,Q0,F）, 语
言 L=L(NDAM)С∑*，
?构造 FSAM′=（ Q′,∑,δ′,q0′,F′）,
其中
?Q′=2Q；
? δ′（ p,x） =U{δ(q,x)|q∈ p}； p∈ Q′，
x∈ ∑，
? 即 δ′（ {q1,q2,… qn},x）
? ={δ(q1,x),δ(q2,x),… δ(qn,x)}
? q0′= Q0∈ Q′，
? F′={p′|p′∈ Q′
且 p′∩F≠Φ}СQ′，
? 即把 NDAM的一个状态集合当作是 FSAM
的一个状态 。
? 则 L=L(NDAM)=T(FSAM′)。 证毕 。
? 根据定理可知, NDAM和 FSAM是可以互
相转换的, 是等价的；它们接收的语言类
是完全一致的, 都是 FSL（ 右线性语言 ）
? 语言 L={ w| w∈ {a,b,c}+,且 w中最后一个
字母与第一个字母相同 }
? 1） 给出该语言的正则表达式； 2） 构造
NDAM接受该语言； 3)将 NDAM转换为等
价的 FSAM。
? 解,1)该语言的正则表达式,
? a(a+b+c)*a+b(a+b+c)*b+c(a+b+c)*c
? 语言 L={ w| w∈ {a,b}+,且 w中倒数第二个字母肯
定在前面出现过 }
? 1） 给出该语言的正则表达式； 2） 构造 NDAM
接受该语言； 3)将 NDAM转换为等价的 FSAM。
? 解,1) 该语言的正则表达式,
? (a+b)*a(a+b)*a(a+b)+ (a+b)*b(a+b)*b(a+b)
?,构造有限状态自动机 M，识别 {0,1}上
的语言，该语言的每个字符串必须包含子
串 00。
? 正则表达式为,(0+1)*00(0+1)*
? 构造有限状态自动机 M，识别 {0,1}上的
语言，该语言的每个字符串必须包含子串
001。
? 正则表达式为,(0+1)*001(0+1)*
? 构造有限状态自动机 M，识别 {0,1}上的
语言，该语言的每个字符串必须不包含子
串 001。
? 构造有限状态自动机 M，识别 {0,1}上的
语言，该语言的每个字符串以 0开头，以 1
结尾。
? 构造有限状态自动机 M，识别 {0,1}上的
语言，该语言的每个字符串若以 1结尾，
则该字符串长度为偶数，若以 0结尾，则
该字符串长度为奇数。
? 定理 6-40 每个右线性语言是一个 FSL。
? 证明：
? L是右线性语言, 且 L=L(G),G=（ ∑,V,S,P）
（ 首先将文法 G中的空串产生式要消除 ）, 构造
NDAM,方法是将文法的非终结符当作 NDAM
的状态, 并且增加一个接收状态 q（ 若文法 G中
有 S→ε, 即 ε∈ L,则开始状态 S也是接收状态 ）
使得
? NDAM=（ Q,∑,δ,Q0,F）, 其中：
? Q=V U {q} Q0={S} F={q}
? δ(A,x)={B|B∈ V,且 A→xB 在 P中 } U
{q|A→x 在 P中 }；
? 所以, L=L(G)=L(NDAM)；
? 而 NDAM又和 FSAM是等价的, 所以, 一
个右线性语言也是一个 FSL。 证毕 。
? 总之, 右线性语言和 FSL是等价的, 只不
过是从不同的角度来对语言进行的描述 。
? 右线性文法产生右线性语言；
? 注意：
? NDAM适于构造, 包含子串 …,,,以
串 … 开始,,, 串以 … 结束,,, （ 倒数 ）
第 … 个字母是 …”,, 满足条件 …” 的语言 。
反之，应该构造 FSAM。
?
?定义 6-43 带有 ε动作的有限状态自动
机
?带有 ε动作的有限状态自动机是一个
五元式,ε- M=(Q,∑,δ,Q0,F)
?其中：
?Q,∑,Q0,F的含义同 NDAM。
?δ是 Q× ∑U{ε}→ 2Q的状态转换函数,
δ(q,x)СQ或 δ(q,ε)СQ
?即 δ(q,x)={p1,p2,p3,…, pm}，
表示自动机在读入字母 x后, 自动机
的状态可以选择地改变为 p1,p2，
p3,…, 或者 pm,并将读头向右移动
一个单元而指向了下一个字符；
?δ(q,ε)={p1,p2,p3,…, pm},表
示自动机在状态 q时, 不读入任何字
母, 自动机的状态可以选择地改变为
p1,p2,p3,…, 或者 pm,并且读头
不进行移动, 而仍然指向当前非空字
符；
? 使用带有 ε动作的有限状态自动机接收该
语言：
? L={0*1*2*},即 L={0n1m2k|n,m,k>=0}
?对于上例, 对应的 δ函数为：
?δ(q0,0)={q0} δ(q0,ε)={q1}
?δ(q1,1)={q1} δ(q1,ε)={q2}
?δ(q2,2)={q2}
?注意：
? 带有 ε动作的有限状态自动机一定
是 NDAM。 一般, 记为 ε-NDAM或 ε-
M。
? 定义 6-44
? 在一个带有 ε动作的有限自动机中，对于
任意状态 q，从 q接收空串 ε后能够到达的
状态集记为 ε-CLOSURE(q)。
? ε-CLOSURE(q)={p|从 q到 p有一条标记为
ε的路 }
?在一个带有 ε动作的有限自动机中,
对于状态 q,它的 ε-CLOSURE（ q）
是由下述规则确定的状态集：
? （ 1） q在 ε-CLOSURE（ q） 中；即任意
状态 q接收空串 ε,至少都能保持状态 q不
变；
? （ 2） 如果 p在 ε-CLOSURE（ q） 中, 则
δ(p,ε)也都在 ε-CLOSURE（ q） 中；
? （ 3） 重复 （ 2）, 直到 ε-CLOSURE（ q）
中状态不再增加为止 。
?注意：
?ε-CLOSURE（ q） 与 δ（ q,ε） 不同 。
? 定理 6-48
? 如果语言 L被一个带有 ε动作的有限状态自
动机接收, 则该语言 L也能够被一个不带 ε
动作的有限状态自动机接收 。
? 6.6 有限状态自动机的一些变形
? 6.6.1双向的有限状态自动机
在处理输入串的过程中, 双向的有限状态自动
机的读头可以向右移动一个单元；也可以向左
移动一个单元；当然, 读头也可以不移动 。
? 6.6.2带有输出的有限状态自动机
实现这类模型的两种不同的带输出的有穷自动
机 -–Moore机和 Mealy机
有限状态自动机和有限状态语言
? 已经介绍过从产生语言的角度定义语言的
形式；下面从识别语言的角度来定义语言。
? 有限状态自动机 (FSM,finite state
machine”或者 FSA,finite state
automaton”)是为研究有限内存的计算过
程和某些语言类而抽象出的一种计算模型。
? 有限状态自动机拥有有限数量的状态，每
个状态可以迁移到零个或多个状态，输入
字串决定执行哪个状态的迁移。有限状态
自动机可以表示为一个有向图 (称之为状
态转换图 )。
? 有限状态自动机是自动机理论的研究对象。
? 有多种类型的有限状态自动机：接受器判
断是否接受输入；转换器对给定输入产生
一个输出。常见的转换器有 Moore机与
Mealy机。 Moore 机对每一个状态都附加
有输出动作,Mealy 机对每一个转移都附
加有输出动作。
? 有限状态自动机还可以分成确定与非确定
两种。非确定有限状态自动机可以转化为
确定有限状态自动机。
? 有限状态自动机识别的语言是正则语言
RL。
? 有限状态自动机除了它在理论上的价值，
还在数字电路设计、词法分析、文本编辑
器程序等领域得到了应用。
6.1 有限状态自动机
? 有穷状态自动机是具有离散输入和输出的系统的
一种数学模型。其主要特点有以下几个方面：
? (1)系统具有有穷个状态，不同的状态代表不同的
意义。按照实际的需要，系统可以在不同的状态
下完成规定的任务。
? (2)我们可以将输入字符串中出现的字符汇集在一
起构成一个字母表。系统处理的所有字符串都是
这个字母表上的字符串。
? (3)系统在任何一个状态下，从输入字符串中读
入一个字符，根据当前状态和读入的这个字符
转到新的状态。
? (4)系统中有一个状态，它是系统的开始状态。
? (5)系统中还有一些状态表示它到目前为止所读
入的字符构成的字符串是语言的一个句子
? 有限状态自动机物理模型如图 6-1所示。
? 一个输入存储带，带被分解为单元，每个单元
存放一个输入符号（字母表上的符号），整个
输入串从带的左端点开始存放，而带的右端可
以无限扩充；
? 一个有穷状态控制器（ FSC），该控制器的状
态只能是有穷多个； FSC通过一个读头和带上
单元发生耦合，可以读出当前带上单元的字符。
初始时，读头对应带的最左单元，每读出一个
字符，读头向右移动一个单元（读头不允许向
左移动）。
? 有限状态自动机的一个动作为：
? 读头读出带上当前单元的字符； FSC根据
当前 FSC的状态和读出的字符，改变 FSC
的状态；并将读头向右移动一个单元。
? 有限状态自动机的动作简化为：
? FSC根据当前的状态和当前带上的字符，
进行 FSC状态的改变。
定义 6-1 有限（有穷）状态自动机（接收机）
的定义
? 字母表 ∑上的有限状态接收机（ FSAM）是
一个五元式,FSAM=（ Q,∑,δ,q0,F），
? 其中：
? Q是一个有限状态的集合；
? ∑是字母表，也就是输入带上的字符的集合；
? q0∈ Q是开始状态；
? FСQ是接收状态（终止状态）集合；
? δ是 Q× ∑→Q 的状态转换函数，即 δ(q，
x)= q′；代表自动机在状态 q时，扫描字符
x后到达状态 q′。
? 理论上，有限状态自动机的状态转换函数
的个数应该为 |Q|*|∑|。因为对于 Q中的每
个状态，都应该定义扫描字母表 ∑上的每
个字母的状态转换函数。
? 例 6-2 有限状态自动机 FSAM=（ { q0,q1}，
{0,1},δ,q0,{q0}），其中 δ为：
? 表示为函数形式：
? δ(q0,0)=q1； δ(q0,1)=q1；
? δ(q1,0)= q1； δ(q1,1)= q0；
? 或者表示为状态矩阵的形式。如图 6-2所
示。
? Q 0 1
? q0 q1 q1
? q1 q1 q0
?
? 或者表示为状态图的形式。如图 6-3所示。
? 状态图是一个有向、有循环的图。一个节点
表示一个状态；若有 δ(q,x)= q′，则
? 状态 q到状态 q′有一条有向边，并用字母 x作
标记。
? 一个圆圈代表一个状态,’ → ’ 指向的状
态是开始状态，两个圆圈代表的状态是接
收状态；在比较明确的情况下，可以用状
态图表示一个有限状态自动机，而有向边
的数目就是状态转换函数的个数。
6.2 有限状态自动机识别语言
? 定义 6-3 有限状态自动机接收串的定义
? 对于有限状态自动机 M,给定字母表 ∑ 上
的串 w=w1w2… wn；初始时, 自动机 M处于开
始状态 q0；从左到右逐个字符地扫描串 w；
在 δ (q0,w1)= q1的作用下, 自动机 M处于
状态 q1,在 δ (q1,w2)=q2的的作用下, 自
动机 M处于状态 q2,… ；
? 当将串 w扫描结束后, 若自动机处于某一
个接收状态, 则称有限状态自动机能够接
收 （ 识别 ） 串 w。 对于自动机而言, 从开
始状态开始, 在扫描串的过程中, 状态逐
个地变化, 直到某个接收状态, 我们把状
态的变化过程称为自动机的一条路径, 而
这条路径上所标记的字符的连接, 就是自
动机所识别的串 。
?定义 6-4 有限状态自动机接收的语言
的定义
?对于字母表 ∑ 上的有限状态自动机 M，
它能识别的所有串的集合, 称为自动
机 M能识别的语言 。 记为 L(M)。
?定义 6-5 扩展的状态转换函数的定义
?给定 FSAM,定义扩展的状态转换函数
δ *,Q× ∑ *→Q 为,δ *（ q,w） =q′
?即自动机在一个状态 q时, 扫描串 w后
到达唯一确定的状态 q′ 。
?定义 6-6 扩展的状态转换函数的形式
定义
?δ *（ q,ε ） =q；
?δ *（ q,x） =δ （ q,x） ；其中 x
是一个字母；
?对于串 w=α x（ x是一个字母, α 是一
个字符串 ） ；
?δ *（ q,w）
?=δ *（ q,α x）
?=δ （ δ *（ q,α ）, x） ；
?或者：对于串 w= xα （ x是一个字母,
α 是一个字符串 ） ；
?δ *（ q,w）
?=δ *（ q,xα ）
?=δ *（ δ （ q,x）, α ）
?定义 6-7 FSAM接收的语言的定义
?L(M)表示被 FSAM=（ Q,∑, δ, q0，
F） 接收的语言, 它在字母表 ∑ 上,
即 L(M） С ∑ *,则
? L(M） ={w|w∈∑ *且 δ *（ q0,w）
∈ F}。
?若语言 LС ∑ *,对于某个有限状态自
动机 M,有 L=L(M),则称语言 L为一个
有限状态语言 （ FSL） 。
定义 6-8 有限状态自动机的瞬
时描述（格局）的定义
?瞬时描述是一个二元式,qy； y∈∑ *，
?其中：
?y是输入带上还没有被扫描到的字符
串, FSC当前状态为 q,读头将马上扫
描 y串的最左边第 1个符号 。
? 格局可以发生转换 （ 改变 ）, 格局发生转
换的原因是由于 δ 函数的一次作用 。
? 如果当前格局为,qar,有 δ 函数,δ (q，
a)= q′, 则下一格局为,q′ r ；
? 格局的转换可以记为,qar => q′ r；
?有限状态自动机初始格局为,q0w；
? 接收格局为,qα ε
?其中,
?q0是开始状态,qα 是某个接收状态；
?使用 =>*代表格局的多次转换 。
?也可以使用格局的转换方式定义有限
状态自动机接收的语言 。
?有限状态自动机接收的语言 L(M)={w|
q0w =>* qα ε ； w∈∑ *且 qα ∈F} 。
? 定义 6-9 有限状态自动机停机的定义
? 有限状态自动机在下面两种情况下停机：
? （ 1） 有限状态自动机将输入串扫描结束时, 或
? （ 2） 有限状态自动机的当前格局为,qar,而
有限状态自动机没有对应的 δ 函数的定义, 即
δ (q,a)=？ （ 此时, 一定没有扫描完输入串 ）
注意 1：
?有限状态自动机停机时, 并不一定接
收扫描过的串 （ 已经读入的符号串 ） ；
?有限状态自动机将输入串扫描结束停
机时, 如果有限状态自动机处于某一
个接收状态, 则表示接收整个串；
? 有限状态自动机将输入串扫描结束停机时, 如
果有限状态自动机没有处于任何的接收状态,
则表示不接收整个输入串；
? 有限状态自动机没有扫描完整个输入串就停机,
一定不会接收整个输入串；如果此时有限状态
自动机处于某一个接收状态, 则说明已经扫描
过的串 （ 是整个串的子串, 而不是整个输入串 ）
能够被有限状态自动机接收 。
注意 2:
? 有限状态自动机的某个状态 q,如果对于字母表
上的字母 x没有对应的 δ 函数的定义, 可以省略
掉该 δ 函数；或者定义一个特殊的状态：陷阱
状态 qt。
? 对于陷阱状态, 定义 δ (q,x)=qt。
? 陷阱状态 qt,仅仅有入口边, 没有出口边, 一定
不是开始状态 。
? 此时, δ 函数的个数 = |Q| * |∑| 。
? 定理 6-10 每个 FSL都是一个右线性语言 。
? 证明思路：
? 假设 L是字母表 ∑ 上的有限状态语言, 且
L=L(FSAM）, FSAM=（ Q,∑, δ, q0，
F）, 构造右线性文法 G=（ ∑, Q,q0,P）
（ 将自动机的状态当作是文法的非终结
符 ）, 其中 P为：
?{q→xq ′ |δ （ q,x） =q′ }
U{ q→x| δ （ q,x） ∈ F }
?特别地, 若开始状态也是接收状态,
则有 q0→ ε ；
? 对于串 w=w1w2… wn：
? 自动机 M,则文法有
? δ（ q0,w1） =q1 q0→w 1q1；
? δ（ q1,w2） =q2 q1→w 2q2；
? … …
? δ（ qn-2,wn-1） =qn-1 qn-2→w n-1qn-1
? δ（ qn-1,wn） =qn qn-1→w nqn
? 或 qn-1→w n
? （ qn是接收状态 ）
? 所以
? 对自动机 M,对文法：
? δ*（ q,α） = q′ q=>*αq′
? δ*（ q0,w） ∈ F q0=>*w
? FSL={（ 0,1） 0*1}*,接收该语言的有限状态自
动机
? 构造右线性文法产生该语言：
? q0→ 0q1|1q1|ε
? q1→ 1q0|0q1|1
定理 右线性语言对补运算是封
闭的
? 证明：
? 假设 L1是字母表 ∑ 上的有限状态语言, 且
L1=L(FSAM1),FSAM1=（ Q,∑, δ, q0,F）, 而
FSAM2=（ Q,∑, δ, q0,Q） 接收的语言是右线
性语言 L1的对应的全集 。
? 对 L1 的 补 运 算 得 到 的 语 言 L2=L(FSAM′ ),
FSAM′ =（ Q,∑, δ, q0,Q-F）, 所以 L2也是
FSL语言 （ 右线性语言 ） 。 证毕 。
? 注意：
? 此时的 FSAM1的 δ 函数的个数 = |Q| * |∑| ；即
需要陷阱状态 。
?
6.3 有限状态自动机识别语言的例子
? 例 6-12 接收语言 L={ab}的有限状态自动机
思考
? 如果将该自动机的所有状态都设置为接收
状态 （ 包括陷阱状态 ）, 那么, 自动机接
收的语言是什么？
? 如果将该自动机的接收状态和非接收
状态对调, 即将状态 S,M,和陷阱状态 qt
都设置为接收状态, 而将原来的接收状态
F设置为非接收状态, 那么, 自动机接收
的语言是什么？
? 构造有限状态自动机 M,识别 {0,1}上的
语言 L={x000y|x,y∈{ 0,1}*}。
? 分析：
? 语言 L={x000y|x,y∈{ 0∈ 0∈{ 0,1}*}，
该语言的特点是语言中的每个串都包含连
续的 3个 0（ 即每个串都包含子串 000）,
? 因此, 对于任何输入串, 有限状态自动机
的任务就是要检查该输入串中是否存在子
串 000,一旦发现输入串包含有 000,则表
示输入串是个合法的句子 （ 是属于语言中
的一个串 ）, 因此, 在确认输入串包含
000后, 就可以逐一地读入输入串的后面
的字符, 并接收该输入串 。
?问题的关键是如何发现子串 000。
?由于字符是逐一读入的, 当从输入串
中读入一个 0时, 它就有可能是 000子
串的第 1个 0,就需要记住这个 0；如
果紧接着读入的是字符 1,则刚才读
入的 0就不是子串 000的第 1个 0,此时,
需要重新寻找 000子串的第 1个 0；
?如果紧接着读入的还是字符 0,它就
有可能是 000子串的第 2个 0,也就需
要记住这个 0,继续读入字符, 如果
还是 0,则表明已经发现子串 000,否
则, 需要重新寻找子串 000。
FSC的状态极其意义
? q0,有限状态自动机的开始状态；也是重新寻找
子串 000时的状态
? q1,有限状态自动机读到第 1个 0,有可能是子
串 000的第 1个 0；；
? q2,有限状态自动机在 q1后又读到 1个 0（ 读到连
续的 2个 0） ；
? q3,有限状态自动机在 q2后又读到 1个 0（ 读到连
续的 3个 0） ； 惟一的接收状态 。
?因此, 基本的状态转移函数为：
? δ (q0,0)=q1
? δ (q1,0)=q2
? δ (q2,0)=q3
?其他状态转移函数为：
? δ (q0,1)=q0
? δ (q1,1)=q0
? δ (q2,1)=q0
? δ (q3,0)=q3
? δ (q3,1)=q3
? 构造有限状态自动机 M, 识别 {0, 1}上的语言
L={x001y|x,y∈{ 0,1}*}。
? 分析：
? 语言 L={x001y|x,y∈{0∈0∈{0, 1}*}，该语言的特点
是语言中每个串都包含子串 001，因此，对于任何输入
串，有限状态自动机的任务就是要检查该输入串中是否
存在子串 001，一旦发现输入串包含有 001，则表示输入
串是个合法的句子（是属于语言中的一个串），因此，
在确认输入串包含 001后，就可以逐一地读入输入串的
后面的字符，并接收该输入串。
? 构造有限状态自动机 M，识别 {0,1}上的语言
L={x000|x∈{0, 1}*}
? 构造有限状态自动机 M，识别 {0,1}上的语言
L={x000}U{x001}，其中 x∈{0, 1}*。
? 构造有限状态自动机 M，识别 {0,1}上的语言
L={02k+3m|m,k>=0}。
? 实际上：
2k+3m可以表示任意的非负整数（除 1外）
? 思考：
? 构造有限状态自动机 M,识别 {0,1}上的语言
L={02k+3m|m,k>0}。
?构造有限状态自动机 M，识别 {0,1}
上的语言，该语言的每个字符串以 0
开头，以 1结尾。
?构造有限状态自动机 M，识别 {0,1}
上的语言，该语言的每个字符串不包
含 00子串（语言允许 ε ）。
?思考：
? 若 语言不允许 ε 。
? 构造有限状态自动机 M，识别 {0,1,2}上
的语言，该语言的每个字符串代表的数字
能整除 3。
? 分析：
? 如果一个十进制整数的所有位的数字的和
能够整除 3,那么, 这个十进制整数本身
就能够整除 3；
? 一个十进制整数除以 3,余数只能是 1,2
和 0（ 余数为 0,则表示该数能够整除 3） ；
? 将整数当作一个字符串, 从左到右逐一地读入；
? 使用 3个状态分别代表已经读入的数字的和除以
3的不同的余数的情况：
? q0：已经读入的数字的和除以 3，余数为 0；
? q1：已经读入的数字的和除以 3，余数为 1；
? q2：已经读入的数字的和除以 3，余数为 2；
?
? 则扫描子串 w后, 处于某个状态, 读入当前数字,
有限自动机的状态转换情况为：
? q0：
? 在此状态读入 0,引导自动机到达下一状态的输
入串为 w0，,w0的各位数字和除以 3,余数为 0。
所以, 自动机在 q0状态读入 0,应该继续保持 q0
状态；
?
? 在此状态读入 1,引导自动机到达下一状态的输
入串为 w1,w1的各位数字和除以 3,余数为 1。
所以, 自动机在 q0状态读入 1,应该到达 q1状态；
? 在此状态读入 2，引导自动机到达下一状态
的输入串为 w2,w2的各位数字和除以 3，余数为
2。所以，自动机在 q0状态读入 2，应该到达 q2状
态；
? …
?对于状态转换图，有一些基本的等价
替换 (参看教材）。
定义 set(q)
?有限状态自动机 FSAM=（ Q,∑, δ,
q0,F）, 对于状态 q,q∈Q ；能将
有限状态自动机从开始状态转换到 q
状态的所有字符串的集合为：
?set(q)={w|w∈∑ *,δ (q0,w)=q}
?则 有限状态自动机 FSAM接收的 语言可
以定义为：
L（ M） =Uset(q)
其中,q∈F
? 一般地, 对于任意一个有限状态自动机
FSAM=（ Q,∑, δ, q0,F）, 可以定义
关系 R,若 x,y∈∑ *, 则 xRy当且仅当
x∈set(q) 且 y∈set(q), 其中,q∈Q 。
? 该关系是集合 ∑ *上的一个等价关系, 利
用该关系, 可以将 ∑ *划分为不多于 |Q|个
的等价类 。
?有限状态自动机可以按照语言的特点
给出字母表 ∑ *的一个划分, 这种划
分相当于 ∑ *上的一个等价分类, 有
限状态自动机的每个状态实际上对应
着一个等价类 。 所以, 利用一个状态
去表示一个等价类是考虑问题 （ 构造
有限状态自动机 ） 的一条有效思路 。
?例构造有限状态自动机 M，识别 {0,1，
2,4,5,6,7,8,9}上的语言，该
语言的每个字符串代表的数字能整除
3。
? 仍然只使用 3个状态分别代表已经读入的
数字的和除以 3的不同的余数的情况：
? q0：已经读入的数字的和除以 3，余数为 0
的输入串的等价类；
? q1：已经读入的数字的和除以 3，余数为 1
的输入串的等价类；
? q2：已经读入的数字的和除以 3，余数为 2
的输入串的等价类；
?构造有限状态自动机 M，识别 {0,1}
上的语言，该语言的每个字符串挡成
二进制数时，代表的数字能整除 3。
? 可能的一个想法是希望构造出的有限状态
自动机在读入 0,1串 （ 二进制串 ） 的过程
中, 按照二进制的解释, 计算出它对应的
十进制数, 再判断是否能整除 3,由于二
进制串有无穷多个, 要计算出每个二进制
串的 （ 十进制 ） 值, 也就需要无穷多个状
态；这种想法是不可取的 。
?有限状态自动机的每个状态实际上对
应着一个等价类 。 所以, 利用一个状
态去表示一个等价类；除以 3的余数
只能为 0,1和 2,使用 3个状态分别代
表已经读入的数除以 3的不同的余数
的等价类：
?q0：已经读入的数除以 3，余数为 0的
输入串的等价类；
?q1：已经读入的数除以 3，余数为 1的
输入串的等价类；
?q2：已经读入的数除以 3，余数为 2的
输入串的等价类；
?因为不能接收空串, 所以, 还需要一
个开始状态 qS。 …
?构造有限状态自动机 M,识别 {0,1}
上的语言 L={0n1m2k|n,m,k>=1}。
?该语言的串的特点是, 0在最前面, 1
在中间, 2在最后, 0,1和 2不能交叉,
顺序也不能颠倒, 并且 0,1和 2的个
数都至少为 1个；需要 4个状态：
? q0：开始状态，等待接收第 1个 0；
? q1：已经读入第 1个 0，等待接收更多的 0；
? q2：已经读入至少 1个 0，且已经接收第 1
个 1，并等待接收更多的 1；
? q3：已经读入至少 1个 0后至少有 1个 1，接
着至少读到 1个 2，并能接收多个 2；
? 构造有限状态自动机 M，识别 {1,2,3}上的语言，
该语言的每个字符串挡成十进制数时，代表的
数字能整除 4 。
? 构造有限状态自动机 M，识别 {0,1,2,3,4,5，
6,7,8,9}上的语言，该语言的每个字符串挡
成十进制数时，代表的数字能整除 4 。
? …
?构造有限状态自动机 FSAM，识别
X={x1,x2,x3,… xM}上的语言，该语
言的每个字符串挡成二进制数
(base=2)或八进制数 (base=8)或十进
制数 (base=10)时，代表的数字能整
除 N。
? 分析：
? 将不同进制的数转换为十进制数后, 除以
N的余数只能为 0,1,2,3… 和 N-1,使用
N个状态分别代表已经读入的数字的和除
以 N的不同的余数的等价类：
? q0：已经读入的数除以 N，余数为 0的输入
串的等价类；该类数为 N*n+0;
? q1：已经读入的数除以 N，余数为 1的输入
串的等价类；该类数为 N*n+1;
? q2：已经读入的数除以 N，余数为 2的输入
串的等价类；该类数为 N*n+2;
? …
? qN-1：已经读入的数除以 N，余数为 N-1的
输入串的等价类；该类数为 N*n+N-1;
?
?注意：因为不能接收空串, 所以, 还
需要一个开始状态 qS。
?qS：在开始状态读入 x时, 进入对应
状态 qx；
?qi：对应已经读入的数 w除以 N,余数为 i
的输入串的等价类；该类数为 N*n+i;
? 当前读入的字符为 x；则 wx表示的十进制
数为：
? base*（ N*n+i） +x
? =N*base*n+base*i+x
?该数对于 N取余数就是 base*i+x对于 N
的余数，若该余数为 j，则相应的状
态就应该从 qi变换为 qj。
?其中：
i=0,1,2,…, N-1。
x为字母 (0~base-1)。
6.4 不确定的有限状态自动机
?每个 FSL都是一个右线性语言, 那么
一个右线性语言是不是一个 FSL呢？
考虑下面的例子：
?接收语言 {aa,ab}的有限状态自动机
? 该自动机识别的语言 L={aa,ab}是一个右
线性语言；但 M不是有限状态自动机,
? 因为,δ （ S,a） = {Q1,Q2},即 δ （ S，
a） 没有到达一个确定的状态 。
? 称这种自动机为不确定的有限状态自动机 。
? FSAM称为确定的有限状态自动机。
6.4.1不确定的有限状态自动机
? 不确定的有限状态自动机 (NDAM)的定义
? NDAM是一个五元式,
NDAM=（ Q,∑,δ,Q0,F）,
? 其中：
? Q是一个有限状态的集合；
? ∑是字母表；
? Q0СQ是开始状态集合；
? FСQ是接收状态 （ 终止状态 ） 集合；
? δ是 Q× ∑→ 2Q的状态转换函数 （ 2Q是指 Q
的幂集 ）, 即 δ(q,x) С2Q ；代表自动机
在状态 q时, 扫描字符 x后到达可能的下一
状态集合 。
? 不确定的有限状态自动机有一个可能的开
始状态集合和可能的下一个状态集合, 其
余的同确定的有限状态自动机 。
? 非确定有限状态自动机与确定有限状态自
动机的唯一区别是它们的转移函数不同 。
确定有限状态自动机对每一个可能的输入
只有一个状态的转移 。 非确定有限状态自
动机对每一个可能的输入可以有多个状态
转移, 接受到输入时从这多个状态转移中
非确定地选择一个 。
? 对于 非确定有限状态自动机,并不是对于
所有的 (q,x)∈ Q× ∑,δ(q,x)都有一个
状态与之对应；并不是对于所有的 (q,x)
∈ Q× ∑,δ(q,a)都只对应一个状态。 δ(q，
x)对应的是状态的一个子集，当这个子集
为空时，表示没有状态与之对应；当这个
子集的元素个数大于 1时，表示有多个状
态与之对应。
?从这个意义上,δ(q,x)仍是通常意
义下的一个函数，只是其值域发生了
改变。当 δ(q,x)对应的所有子集元
素个数为 1时,NDAM退化为 FSAM。
?因此, 在扫描一个串 w时, 经过 NDA
可能会有多条路径, 某些可能会在接
收状态时终止, 某些可能会在非接收
状态时终止；若至少存在一条路径可
以使自动机在扫描串 w后到达接收状
态, 则称串 w能被自动机 NDAM所识
别 。
?对于字母表 ∑上的不确定的有限状态
自动机 M,它能识别的所有串的集合,
称为自动机 NDAM能识别的语言 。 记
为 L(NDAM)。
? 不确定的有限状态自动机扩展状态转换函
数的定义
? 给定 NDAM,定义扩展的状态转换函数 δ*：
2Q× ∑*→ 2Q为
? δ*（ p,w） = Q′,即自动机在状态集合 p
时, 扫描串 w后到达可能的的状态集合 Q′。
? 若 p={ q1,q2,… qn}；
? δ*（ p,ε） =p；
? δ*(p,x)=U{δ（ q,x） |q∈ p； x∈ ∑}；
? ={δ(q1,x),δ(q2,x),…,δ(qn,x)}
? δ*（ p,w） =δ*（ p,xα）
? =U{δ*（ q,α） | q∈ δ*（ p,x） }；
?L(NDAM)表示被不确定的有限状态自
动机 NDAM=（ Q,∑,δ,Q0,F）
所接收的语言, 它在字母表 ∑上, 即
L(NDAM)С∑*,则
?L(NDAM)={w|w∈ ∑*且 δ*（ Q0,w）
∩F!=Φ}。
?它表示输入串 w的集合；在 NDAM的
状态图中, 至少存在一条路径, 以 w
为标记, 能使 NDAM从某个开始状态
到达某个接收状态 。
? 6.4.2不确定的有限状态自动机转换为确定
的有限状态自动机
? 定理 6-31
? ∑*的一个子集 L是一个有限状态语言
（ FSL）, 当且仅当存在 NDAM,使得
? L(NDAM)=L。
证明,=>：
? 若 L是 FSL,则有 FSAM=（ Q,∑,δ,q0，
F）, 且 L=L(M）, 构造
? NDAM=（ Q,∑,δ1,{q0},F）,
? 且 δ1,Q× ∑→ 2Q为：
? δ1（ q,x） ={δ（ q,x） }，
? 即把 FSAM的一个状态当作是 NDAM的一
个状态集合,
? 则 L=L(M） =L(NDAM)。
<=：
?NDAM=（ Q,∑,δ,Q0,F）, 语
言 L=L(NDAM)С∑*，
?构造 FSAM′=（ Q′,∑,δ′,q0′,F′）,
其中
?Q′=2Q；
? δ′（ p,x） =U{δ(q,x)|q∈ p}； p∈ Q′，
x∈ ∑，
? 即 δ′（ {q1,q2,… qn},x）
? ={δ(q1,x),δ(q2,x),… δ(qn,x)}
? q0′= Q0∈ Q′，
? F′={p′|p′∈ Q′
且 p′∩F≠Φ}СQ′，
? 即把 NDAM的一个状态集合当作是 FSAM
的一个状态 。
? 则 L=L(NDAM)=T(FSAM′)。 证毕 。
? 根据定理可知, NDAM和 FSAM是可以互
相转换的, 是等价的；它们接收的语言类
是完全一致的, 都是 FSL（ 右线性语言 ）
? 语言 L={ w| w∈ {a,b,c}+,且 w中最后一个
字母与第一个字母相同 }
? 1） 给出该语言的正则表达式； 2） 构造
NDAM接受该语言； 3)将 NDAM转换为等
价的 FSAM。
? 解,1)该语言的正则表达式,
? a(a+b+c)*a+b(a+b+c)*b+c(a+b+c)*c
? 语言 L={ w| w∈ {a,b}+,且 w中倒数第二个字母肯
定在前面出现过 }
? 1） 给出该语言的正则表达式； 2） 构造 NDAM
接受该语言； 3)将 NDAM转换为等价的 FSAM。
? 解,1) 该语言的正则表达式,
? (a+b)*a(a+b)*a(a+b)+ (a+b)*b(a+b)*b(a+b)
?,构造有限状态自动机 M，识别 {0,1}上
的语言，该语言的每个字符串必须包含子
串 00。
? 正则表达式为,(0+1)*00(0+1)*
? 构造有限状态自动机 M，识别 {0,1}上的
语言，该语言的每个字符串必须包含子串
001。
? 正则表达式为,(0+1)*001(0+1)*
? 构造有限状态自动机 M，识别 {0,1}上的
语言，该语言的每个字符串必须不包含子
串 001。
? 构造有限状态自动机 M，识别 {0,1}上的
语言，该语言的每个字符串以 0开头，以 1
结尾。
? 构造有限状态自动机 M，识别 {0,1}上的
语言，该语言的每个字符串若以 1结尾，
则该字符串长度为偶数，若以 0结尾，则
该字符串长度为奇数。
? 定理 6-40 每个右线性语言是一个 FSL。
? 证明：
? L是右线性语言, 且 L=L(G),G=（ ∑,V,S,P）
（ 首先将文法 G中的空串产生式要消除 ）, 构造
NDAM,方法是将文法的非终结符当作 NDAM
的状态, 并且增加一个接收状态 q（ 若文法 G中
有 S→ε, 即 ε∈ L,则开始状态 S也是接收状态 ）
使得
? NDAM=（ Q,∑,δ,Q0,F）, 其中：
? Q=V U {q} Q0={S} F={q}
? δ(A,x)={B|B∈ V,且 A→xB 在 P中 } U
{q|A→x 在 P中 }；
? 所以, L=L(G)=L(NDAM)；
? 而 NDAM又和 FSAM是等价的, 所以, 一
个右线性语言也是一个 FSL。 证毕 。
? 总之, 右线性语言和 FSL是等价的, 只不
过是从不同的角度来对语言进行的描述 。
? 右线性文法产生右线性语言；
? 注意：
? NDAM适于构造, 包含子串 …,,,以
串 … 开始,,, 串以 … 结束,,, （ 倒数 ）
第 … 个字母是 …”,, 满足条件 …” 的语言 。
反之，应该构造 FSAM。
?
?定义 6-43 带有 ε动作的有限状态自动
机
?带有 ε动作的有限状态自动机是一个
五元式,ε- M=(Q,∑,δ,Q0,F)
?其中：
?Q,∑,Q0,F的含义同 NDAM。
?δ是 Q× ∑U{ε}→ 2Q的状态转换函数,
δ(q,x)СQ或 δ(q,ε)СQ
?即 δ(q,x)={p1,p2,p3,…, pm}，
表示自动机在读入字母 x后, 自动机
的状态可以选择地改变为 p1,p2，
p3,…, 或者 pm,并将读头向右移动
一个单元而指向了下一个字符；
?δ(q,ε)={p1,p2,p3,…, pm},表
示自动机在状态 q时, 不读入任何字
母, 自动机的状态可以选择地改变为
p1,p2,p3,…, 或者 pm,并且读头
不进行移动, 而仍然指向当前非空字
符；
? 使用带有 ε动作的有限状态自动机接收该
语言：
? L={0*1*2*},即 L={0n1m2k|n,m,k>=0}
?对于上例, 对应的 δ函数为：
?δ(q0,0)={q0} δ(q0,ε)={q1}
?δ(q1,1)={q1} δ(q1,ε)={q2}
?δ(q2,2)={q2}
?注意：
? 带有 ε动作的有限状态自动机一定
是 NDAM。 一般, 记为 ε-NDAM或 ε-
M。
? 定义 6-44
? 在一个带有 ε动作的有限自动机中，对于
任意状态 q，从 q接收空串 ε后能够到达的
状态集记为 ε-CLOSURE(q)。
? ε-CLOSURE(q)={p|从 q到 p有一条标记为
ε的路 }
?在一个带有 ε动作的有限自动机中,
对于状态 q,它的 ε-CLOSURE（ q）
是由下述规则确定的状态集：
? （ 1） q在 ε-CLOSURE（ q） 中；即任意
状态 q接收空串 ε,至少都能保持状态 q不
变；
? （ 2） 如果 p在 ε-CLOSURE（ q） 中, 则
δ(p,ε)也都在 ε-CLOSURE（ q） 中；
? （ 3） 重复 （ 2）, 直到 ε-CLOSURE（ q）
中状态不再增加为止 。
?注意：
?ε-CLOSURE（ q） 与 δ（ q,ε） 不同 。
? 定理 6-48
? 如果语言 L被一个带有 ε动作的有限状态自
动机接收, 则该语言 L也能够被一个不带 ε
动作的有限状态自动机接收 。
? 6.6 有限状态自动机的一些变形
? 6.6.1双向的有限状态自动机
在处理输入串的过程中, 双向的有限状态自动
机的读头可以向右移动一个单元；也可以向左
移动一个单元；当然, 读头也可以不移动 。
? 6.6.2带有输出的有限状态自动机
实现这类模型的两种不同的带输出的有穷自动
机 -–Moore机和 Mealy机
