第3 章
有穷状态自动机
第2章从文法的角度,也就是从语言生成的角度研究语言。除了文法之外,也可以用不
同的识别模型,从识别的角度研究语言。本章讨论的是正则语言的识别模型———有穷状态
自动机(FA)。主要内容有确定的有穷状态自动机(DFA),不确定的有穷状态自动机
(NFA),带空移动的有穷状态自动机(ε-NFA),带输出的有穷状态自动机,以及双向有穷状
态自动机。
关于DFA,介绍如何从实际问题抽象出DFA,DFA 的直观物理模型。按照这种抽象,
给出DFA 的形式定义,它接受的句子、语言状态转移图等重要概念。如何构造识别给定语
言的DFA 是本章难点之一。本章通过例子介绍DFA 的构造。
NFA 是DFA 的一种变形。为了构造方便,从基本定义上对DFA 进行了扩充。但是在
扩充之后,它仍然与DFA 等价。
ε-NFA 是对NFA 的进一步扩充。扩充后得到的ε-NFA 与DFA 也是等价的。
DFA,NFA,ε-NFA 是FA 的3种等价形式,它们是正则语言的识别器。在3.5节中,专
门讨论正则文法(RG)与FA 的等价性及其相互转换方法。
带输出的FA 和双向FA 是FA 的另一些变形。其中,带输出的FA 可以根据状态或者
移动输出信息,而双向FA 既允许FA 的读头向右移动,又允许读头向左移动。
由于和FA 相关的内容都是以DFA 的概念为基础的,而且让初学者把一个模
型———形式化模型当成一个自动机去理解,在心理上会遇到较大的障碍,所以,在上述所
列的内容中,DFA的概念不仅是重点,而且还是难点。对DFA 概念的突破,是对其他内
容理解的重要基础。本章的第二个重点内容为DFA,NFA,ε-NFA,RG 之间的等价转换
思路与方法。这些内容,不仅再次讨论了形式模型之间的等价转换问题,而且体现了对
这些形式模型更深层的理解,甚至能使读者体验到这些形式模型之间等价变换思想的闪
光,并且体验大师们当初发现这些等价转换方法尤其是FA 与RG 的等价转换方法所获
得的乐趣。
除了对DFA 概念的理解之外,DFA 和RG 的构造方法、RG 与FA 的等价性证明等也
是比较难以掌握的。
46
形式语言与自动机理论教学参考书(第4版)
3.语言的识别
1
知识点
(1)推导和归约中的回溯问题将对系统的效率产生极大的影响。
(2)作为语言的识别模型,需要5个要素,该模型的每个移动由3个节拍组成:读入它
正注视的字符,根据当前状态和读入的字符改变有穷控制器的状态,将读头向右移动一格。
(3)相应的物理模型为:一个右端无穷的输入带,一个有穷状态控制器,一个读头。
3.有穷状态自动机
2
1.
知识点
(1)FA 是一个五元组
M
=(Q,Σ,q0,F); 由于对任意的(a)∈Q×Σ,
Q
中有唯一
δ,q,
的状态
p
与δ(a) 所以称之为DFA
。
q,
对应,
^ 的定义域Q×Σ* 但对于任意的(a)∈Q×Σ,
(2)虽然
δ
的定义域Q×Σ
是
δ
的真子集, q,
^ 和
δ
(
有相同的值,所以不用区分这两个符号
。
3)L(
M
)x|x∈Σ* q,为
M
接受( 的语言
。
δ
={且δ(x)∈F} 识别
)
(4)FA 的状态转移图
。
(5)DFA 的等价
。
M
。
(6)DFA 的ID 及ID 之间的关系
(7)DFA 的状态只具有有穷记忆能力
。
et(={δ(x)
(8)DFA 的每个状态记忆集合sq)x|x∈Σ*,q0,=q}, 这使得DFAM
=
(Q,δ,F) 该等价关系将Σ* 对于每
Σ,q0,自然地对应于等价关系RM
, 分成有穷多个等价类
,
一个可达状态q,t(就是
q
对应的等价类
。
(9)陷阱状态。(e) (s) q)
(10)将要记忆的内容用作状态的标识,有利于一类DFA 的表示和构造。
2.
主要内容解读
定义31
有穷状态自动机(
Q,Σ,
n,
F)
M
是一个五元组:
finiteautomatoFA)
δ,
其中,
M
=(q0,
Q——
q
称为
M
的一个状态(tt
—状态的非空有穷集合。.q∈Q,sae)。
———输入字母表(t)。输入字符串都是
Σ
上的字符串。
Σ
inputalphabeδ
———状态转移函数(transitionfunction), 有时又称为状态转换函数或者移动函数。
δ:Q×Σ→Q, q,δ(a)
p
表示
M
在状态
q
读入字符a,
对.(a)∈Q×Σ,q,=将状
态变成p,并将读头向右移动一个带方格而指向输入字符串的下一个字符。
有穷状态自动机
q0——iiilsae),也可称为初始状态或者启动状态,q0∈Q。
—
M
的开始状态(ntatt
——
M
的终止状态(F.Q。.q∈F,
F
—finalstate)集合,
q
称为
M
的终止状态。终止
状态又称为接受状态(aceptstate)。
对此定义的理解,需要注意以下几方面:
(1)要求状态集
Q
是非空有穷的,这和要求一个字母表是非空有穷的原因是类似的。
实际上,希望FA描述的是一个语言的处理系统,而每个系统至少要有一个状态。当然,如
果该系统具有无穷多个状态,它就不是当代计算机系统可以“模拟”的了。因此,
Q
必须是
有穷的。
Q×Σ→Q, q,
(
(2)状态转移函数δ:表明对任意(a)∈
Q
×Σ,
Q
中有唯一的状态
p
与
q,a)对应,所以,为了和后面定义的其他类型的FA相区别,才称这里定义的FA为DFA
(deterministicfiniteautomaton)。初学者最容易忽略的问题之一是当检查用状态转移图表
示的FA是否为DFA时,有可能忽略掉δ(a)
q,不对应任何状态这一不满足要求的情况。
尤其是在后面讲过NFA后,更容易错误地认为,只要不存在(使得|δ(a)|>1,
相应的FA就是DFA了。
q,a)∈Q×Σ, q,
(3)开始状态就是FA在正常情况下,开始处理一个输入串的状态。在实际系统的实
现中,当需要此FA再处理另外一个输入串时,它必须重新从这个状态启动,而不管它在处
理完上一个串后处于哪个状态。
(4)虽然
F
中的状态称为终止状态,并不是说
M
一旦进入这种状态就终止了,而是说,
一旦
M
在处理完输入字符串时到达这种状态,
M
就接受当前处理的字符串。在FA处理一
个输入串的过程中,它可能“经过”某些终止状态,但是,如果它在处理完这个输入串后未停
在终止状态,则此串不被FA“认可”。也就是说,FA在决定是否“认可”一个输入串时,并不
考虑它是否曾经在中途经过某一个终止状态,而是根据它处理完该字符串时的当前状态决
定的。据此,将这类状态称为接受状态也许更恰当。
例3-1给出了两个FA,一方面用来作为两个实例,另一方面是给出FA的状态转移函
数的表达方式。由于现在还没有定义什么是FA接受的语言,所以,现在还不能讨论这两个
FA能识别什么语言。但是,如果在给出FA接受的语言的定义后再行举例,新的概念就显
得在一起堆积得太多,不利于学习。
由于语言是由句子,也就是满足一定条件的串组成的,所以,为了定义FA识别的语言,
必须先将
δ
的定义域从Q×Σ
扩充到Q×Σ*上,以便于讨论FA是如何处理字符串的。然
后,考虑如何表示组成语言的句子所需要满足的条件就容易了。对此扩展,读者需要弄明白
为什么不在一开始就直接用
δ
表示扩展的状态转移函数,而是要在证明了对于任意的
(a)∈Q×Σ,^
^
和
:
δ
有相同的值后方可以用同一个符号表示。
q,
δ
将
δ
扩充为δQ×Σ*→
Q
使用的是递归定义,这也是与FA处理字符串的过程一致
的,从而也给今后研究FA处理字符串做了一定的准备。这个定义为:对任意q∈Q,
w
∈
Σ*,
a∈Σ:
(1)δε)=
q
^(
q,。
(^(wa)δ(^(w),)。
其中,第一条是基础,表示FA在不读入任何字符时将保持在原来的状态不变;第二条表示
2)δq,=δq,
a
第
章
47
48
形式语言与自动机理论教学参考书(第4版)
对一个串wa,FA 必须处理完
w
后再处理a,而且处理
a
时所处的状态是处理完
w
后所处
的状态。进一步对
w
展开这个式子,它表示FA 是从左到右处理输入串中的字符,该FA 从
状态
q
开始,首先在状态
q
下处理第一个字符,然后进入一个新状态,再在这个新状态处理
下一个字符,如此下去,直到串中所有字符都被处理完。设x=a1a2…an
,以此形式,这个过
程可以表示为
δ(a1a2…)
q,an
=a1a2…an-a
δ(q,)
δ(1),
δ(δ(a1a2…),1),(n) )
=δ(q,an-an
.
=δ(δ(δ(a1),an-an
δ(δ(q,a2),…),1),)
不妨设
δ(a1)q1,q1,=q2,…,q2,n-=n-δ(n-a)=n
q,=δ(a2)δ(n-a1)q1,q1,nq
则
δ()
q,
a1a2…an
δ(a2…a)
=q1,
n
δ(a3…a)
.
δ(2,)
=q2,
n
=qn-an-1an
δ(1,)
=qn-an
=qn
如果按照ID 的表示方法,这个过程可以表示
为
…
qa1a2…an
a1q1a2…an
a1a2q2a3…an
a1a2…qn-2an-1an
a1a2…an-1
qn-1an
a1a2…anqn
实际上,左侧的字符串是不会再被扫描的,所以,它们是可以不在ID 中反映的。另外,被
FA 处理q过(i) 的a1a2…an
的前缀a1a2…ai
的对应后缀ai+1…an
正好是FA 从状态qi
开始待
处理的内容。
Q,Σ,q0,q,w)∈F,
定义32
设
M
=(δ,F)是一个FA 。对于.x∈Σ*,如果δ(则称
x
被
M
接受,如果δ(则称
M
不接受x。
q,
q,w).F,
称为由
M
接受(识别)的语言
L
。
(
M
)={x|x∈Σ*且δ(w)∈F}
这个定义也可以叙述为:能引导FA 从启动状态出发,最终到达终止状态的字符串是
FA 识别的语言的句子。所有这样的字符串组成的集合为FAM
接受的语言,记作L(
M
)。
定义33
设M1,M2 为FA 。如果L(M1)=L(M2), 则称M1 与M2 等价。
这个定义说明,判定两个FA 是否等价的标准是它们接受的语言是否相同。这和判定
两个文法是否等价一样。另外,表示一个语言的文法可以有多个,识别一个语言的FA 也可
以有多个:如果有一个FA 能识别语言L,那么也可能存在“许许多多”的识别
L
的FA 。
例3-2是真正按照规定的语言构造的第一个DFA,这个DFA 的构造虽然比较简单,但
是却表现出构造DFA 的一个非常重要的方法,这就是DFA 的每一个状态表达不同的意
思。当DFA 到达不同的状态时,表明DFA 当前扫描过的字符串的前缀已经具有语言要求
有穷状态自动机
第
的句子的某种结构。由于DFA 只有有穷个状态,所以,DFA 的状态只具有有穷记忆能力。
3
这就预示着,如果一个语言的结构特征中只有有穷多种需要记忆的信息,则能构造出接受它
章
的DFA 来。
状态转移图是DFA 的一个非常直观的表示,当熟悉这种表示时,通过画出接受一个语
言的DFA 的状态转移图来完成这个DFA 的构造是最为方便的。由于状态转移图具有直
观性,而这种直观性非常便于人们对其表达内容的理解,所以,对人们来说,使用这种表示方
法进行“规模”不是特别大的DFA 的构造是最为方便和有效的。所以,往往只画出DFA 的
状态转移图就可以了。FA 的状态转移图的定义如下。
49
定义34
设
M
=(Σ,q0,为一个FA,
Q,δ,F) 满足如下条件的有向图被称为
M
的状
态转移图(:
transitiondiagram)
(1)q∈
Q
.
q
是该有向图中的一个顶点
。
(2)δ(a)p.图中有一条从顶点
q
到顶点
p
的标记为
a
的弧。
q,
=
(3)q∈F.标记为
q
的顶点被用双层圈标出
。
(4)用标有
S
的箭头指出
M
的开始状态。
状态转移图又可以称为状态转换图。有时,状态转移图中会存在一些并行的弧:它们从
同一顶点出发,到达同一个顶点。对这样的并行弧,可以用一条有多个标记的弧表示。
通过例3-3DFA 的构造,总结出以下几点注意事项:
(1)定义FA 时,只给出FA 相应的状态转移图就可以了。
(2)对于DFA 来说,并行的弧按其上标记字符的个数计算,对于每个顶点来说,它的出
度恰好等于输入字母表中所含字符的个数。这一点提醒读者,第一,当完成一个DFA 的构
造后,至少需要检查一下,看每个顶点的出度是否正确;第二,在构造DFA———画DFA 的状
态转移图时,需要逐个状态地考虑该状态对应字母表中的每个字母的转移方向,这在许多时
候会给构造提供启发。
(3)字符串
x
被FAM
接受的充分必要条件是在
M
的状态转移图中存在一条从开始
状态到某一个终止状态的有向路,该有向路上从第一条边到最后一条边的标记依次并置而
构成的字符串x。此路的标记简称为x。
(4)一个FA 可以有多个终止状态。实际上,每个终止状态代表语言中句子的不同分
类。例如,主教材图3-5的终止状态q3 和q4 分别代表语言{x000|x∈{0,1}*}∪{x001|
x∈{0,1}*}的以000 结尾的句子组成的类和以001 结尾的句子组成的类。
图3接受语言{x∈{0,1}*}∪{x∈{0,1}*}的DFA
-
5
x000|x001|
FA 的即时描述及其相互之间的关系
提供了描述FA 识别一个输入串的更为方便的
过程,其定义如下。
形式语言与自动机理论教学参考书(第4 版)
5 0
定义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 的所有ID 集上的二元关系,它与M 定义的移动有关,而且可用nM
,
*M
,+M
分别表示M ( )n ,M ( )* ,M ( )+ ,当意义明确时,也可以直接用,n , * , + 表示
M ( )n ,M ( )* ,M ( )+ 。
α nM
β:表示M 从IDα 经过n 次移动到达IDβ,即M 存在ID序列α1,α2,…,αn-1,使
得α Mα1,α1M α2,…,αn-1Mβ。
当n=0时,有α=β。即α 0M
α。
α +M
β:表示M 的ID从α 经过至少一次移动变成β。
α *M
β:表示M 的ID从α 经过若干步移动变成β。
需要注意,在第9章图灵机中,也定义有类似的ID,只不过在图灵机中,qi 左侧的字符
串(即a1a2…an 的前缀)是有可能被再次扫描的,而在这里它们是不会被再次扫描的。
定义3-6 设M =(Q,Σ,δ,q0,F)为一个FA,对.q∈Q,能引导FA 从开始状态到达
q 的字符串的集合为
set(q)={x|x∈Σ*,δ(q0,x)=q}
这个定义的引入,是为了明确地将DFA 的状态和DFA 所确定的关于Σ* 的等价类对
应起来,以深入理解DFA。根据这种对应关系,任意一个FAM =(Q,Σ,δ,q0,F)就自然有
了等价关系RM 。
对.x,y∈Σ*,xRMy ..q∈Q,使得x∈set(q)和y∈set(q)同时成立。
之所以说利用这个关系可以将Σ* 划分成不多于|Q|个等价类,主要是因为DFA 中可
能有不可达状态。但是,对NFA,这个结论是不成立的。
例3-4给出了一种根据“主体框架”构造DFA 的思路,同时引入了陷阱状态的概念及其
用法。通
过例3-4和例3-5进一步表明如何利用状态的有穷存储功能构造DFA,尤其是在
例3-5中,先分析出可以按照同余类来分等价类这一关键点,然后将等价类(同余类)与状
态对应起来,并考虑用3所确定的输入串所处的等价类及其等价类之间的变换关系,来确定
相应的DFA 的状态之间应该如何转移。
有穷状态自动机
例3-6将要记忆的内容用作对状态的标识,这种方法在表示一类DFA 及其构造思想
时
是非常有效的
。
ε]———
M
还未读入任何字符
。
q[
——陷阱状态
。
qt —
q[—
M
记录有
i
个字符,a1,ai∈{0,
a1a2…ai]——1≤i≤5 。其中,a2,…,1}。
3.不确定的有穷状态自动机
3
3.1
作为对DFA
的修改
3.
知识点
希望对于所有的(a)∈Σ×Q,q,对应的是
Q
的一个子集。并认为这种扩展了
q,δ(a)
的FA 在于允许它在任意时刻可以处于有穷多个状态,这样一来,则有
(1)并不是对于所有的(a)∈Σ×Q,q,都有一个状态与它对应。
q,δ(a)
(2)并不是对于所有的(a)∈Σ×Q,q,只对应一个状态。
q,δ(a)
Q
的有穷性保证了2Q
的有穷,使得这种FA 仍然是具有有穷个状态的。
也可以将这种扩充看成是允许FA 具有“智能”,该“智能”足以使FA 在一个状态下,根
据当前读入的字符在集合δ(a)
q,中选择一个正确的状态。
3.2
NFA
的形式定义
3.
1.
知识点
(1)NFA 与DFA 相比,只是状态转移函数的值域由
Q
变成了2Q 。
(2)DFA 是NFA 的特例。
q0,
(3)
x
被
M
接受,当且仅当δ(x)∩F≠.
。
2.
主要内容解读
定义37
不确定的有穷状态自动机(non-deterministicfiniteautomaton,NFA)
M
是
一个五元组:
Σ,q0,
其中,
M
=(Q,δ,F)
Q,Σ,
F
的意义同DFA 。
q0,
δ——tastoucin), Q×
—状态转移函数(rniinfnto又称为状态转换函数或者移动函数。δ:
Σ→2Q
,对.(a)∈Q×Σ,q,={p2,…,pm
表示
M
在状态
q
读入字符
q,δ(a)p1,}
a,可以有选择地将状态变成p1,p2,…, 或者pm
,并将读头向右移动一个带方格
而指向输入字符串的下一个字符。
原来为DFA 定义的状态转移图、状态对应的等价类、即时描述等对NFA 都是有效的。
^:,
与DFA 相同,将
δ
扩充为δQ×Σ*→2Q
。对任意q∈Q,w∈Σ* a∈Σ:
^(
(1)δε)q}。
q,={
第
章
51
52
形式语言与自动机理论教学参考书(第4版)
(^(^(w), 使得p∈δ()}
。
而且由于对于任意q∈Q,
r,
2)δq,wa)={p|.r∈δq,
a
a∈Σ:
δq,=q,
所以,可以用
δ
代替
δ
^(a)δ(a)
^。
由于对.(w)∈Q×Σ*δ(w) 因此, 才进一步扩充δ
q,,q,是一个集合, 为了叙述方便
,
的定义域:δ:2Q
×Σ*→2Q
。对任意P.Q,w∈Σ*
,
δ(P,w)δ(w)
=∪ q,
q∈
P
考虑到对.(:
δ({w)=q,
q,w)∈Q×Σ*
q},δ(w)
所以,可以不区分
δ
的第一个分量是一个状态还是一个状态集合。于是,对任意q∈Q,
w
∈
Σ*,
a∈Σ,可以得到
δ(q,wa)δ(q,a)=δ(w),
从而,对输入字符串a1a2…an
有
n
=…δ(a1),aδ(q,a1a2…a)δ((δ(q,a2),…),
n
)
Q,Σ,q0,q0,x)∩F≠
定义38
设
M
=(δ,F)是一个NFA 。对于.x∈Σ*,如果δ(
., q0,
则称
x
被
M
接受,如果δ(x)∩F=.,则称
M
不接受x
。
L(
M
)x|x∈Σ* q0,x)∩F≠.
}
注意:对于.x∈Σ*,q0,x)是一个集合, 在判定字符串
x
是否被
M
接受时,要
δ(所以,
称为由
M
接受(识别)的语言。
={
即判定δ(
且δx(
)∩F≠. 是否成立。按照状态转移图来
看δ(q0,x)中是否含有终止状态, q0,
说,就是要看在
M
的状态转移图中是否存在从q0 出发到达某一个终止状态的标记为
x
的路。
3.3
NFA
与DFA
等价
3.
1.
知识点
(1)NFA 与DFA 等价是指这两种模型识别相同的语言类。
(2)`DFA 对NFA 的模拟的关键是DFA 用一个状态去对应NFA 的一组状态:[p1,
p2,…,pm
].{p1,p2,…,pm
}。
(3)不可达状态是无意义的。
(4)根据NFA 构造等价的DFA 时,可以只给出DFA 的所有可达状态,从而可以直接
略去关于不可达状态相关的计算。
2.
主要内容解读
3-
1
NFA 与DFA 等价
。
证明要点
:
(
1)构造。
Σ,q0,
设NFAM1=(Q,δ1,F1)
。
有穷状态自动机
第
取DFAM2=(Q2,δ2,[F2)。
Σ,q0],
3
Q2=2Q
,只是暂时将用“{”和“}”把集合的元素汇集成整体的习惯写法改为用“[”和“]”把
章
集合的元素汇集成整体。
F2={[p1,]|{p2,…,p1,}∩F1≠.}
p2,…,p1,}.
Q
且{p2,…,
pmpm
pm
δ2([q2,…,a)p1,].δ1({q2,…,a)p1,}
53
q1,],=[p2,…,q1,},={p2,…,
这实际上给出了构造给定NFA 的等价DFA 的一般方法。显然,这种转换方法是可以“被
自动化”的。由于这种构造方法的一般性,所以,在新构造出的DFA 中,可能存在不可达的状
态。例3-7给出了相应的实例。
由于不可达状态对语言的识别是无用的,所以,需要将它们删除。最好是直接避免因不可
达状态所导致的无用计算。方法是从开始状态[出发,考查
Σ
中的所有符号,逐步地计算出
qn
pmqn
pm
q0]
所有可达的状态及其相应的转移。例3-7给出的是逐步在表中填写表达状态转移函数值的
p
方法
2,…,
。
(2)对任意
]。
x∈Σ*,施归纳于|证明δ1(x)={p2,…,}.δ2([q0],x)=[
x|, q0,p1,pm
p1,
pm
(M1)=L(M2)。
3)证明L(
(和(两步表明了(中所给的构造方法的正确性。因此,今后可以直接用此方法构造
2)3) 1)
给定NFA 的等价DFA,不用再对构造的结果进行证明。
例3-7给出的直接省去不可达状态相关计算的思路,可以用到直接根据NFA 的状态转移
图构造DFA 的状态转移图中。在这里,所有的与不可达状态相关的顶点和弧,都不用在状态
转移图中出现。
图3-
9
希望是接受{x|x∈{1}*,且
x
含有子串00
或11}
0,的FA
下面仍然以图3-9所示的NFA 为例,直接画出与其等价的DFA 的状态转移图。相应的
构造过程如下:
(q0] -a)。
1)先画出只含开始状态[的图39(
图3从开始状态[开始
-9(a) q0]
(q0]关于0和1的转移。
2)考查状态[
q0,q0,q0]
因为δ({q0},0)={q1}, 所以,在图中增加标记为[q1]的顶点,并从标记为[的顶
点到标记为[q1]的顶点画一条标记为0的弧。
q0,
因为δ({q0},1)={q2}, 所以,在图中增加标记为[q2]的顶点,并从标记为[的顶
q0,q0,q0]
点到标记为[q2]的顶点画一条标记为1的弧。此时可得图39(b)。
q0,
形式语言与自动机理论教学参考书(第4版)
54
图39(b) 增加在[状态下的移动
-q0]
(q0,关于0和1的转移。
3)考查状态[q1]
q0,0)q0,q0,
因为δ({q1},q3}, 所以,在图中增加标记为[q3]的顶点,并从标记
为[q1]的顶点到标记为[q1,的顶点画一条标记为0的弧。
={q1,q1,
q0,q0,q3]
因为δ({q1},q2}, 所以,在图中标记为[q1]的顶点到标记为[q2]的顶q0,1)={q0,
c)。
q0,q0,
点画一条标记为1的弧。此时,可得图3-9(
图39() 增加在[状态下的移动
q0,
-cq1]
(q0,关于0和1的转移。
4)考查状态[q2]
因为δ({q2},q1}, 所以,从标记为[q2]的顶点到标记为[q1]的顶点画
q0,0)={q0,q0,q0,
一条标记为0的弧。
={q2,q2,q0,1)q0,q0,
因为δ({q2},q3}, 所以,将标记为[q3]的顶点添入图中,并从标记
q0,q0,q3]
为[q2]的顶点到标记为[q2,的顶点画一条标记为1的弧。此时,可得图3-9(d)。
图39(d) 增加在[q2]状态下的移动
-q0,
(q0,q3]
5)考查状态[q1,关于0和1的转移
。
q0,q1,q0,q0,
因为δ({q3},q3}, 所以,从标记为[q3]的顶点画一条到自身的
标记为0的弧。
1)={q2,q1,q2,q0,q1,q0,q0,q0,
0)={q1,q1,
因为δ({q3},q3}, 所以,从标记为[q3]的顶点到标记为[
q3] -9(
的顶点画一条标记为1的弧。此时,可得图3e)。
有穷状态自动机
第
章
55
图39(增加在[q1,
-e) q0,q3]状态下的移动
(q0,q3]关于0和1的转移。
6)考查状态[q2,
={q1,q2,q1,q0,q2,0)q0,q0,q0,
因为δ({q3},q3}, 所以,从标记为[q3]的顶点到标记为[
q3]的顶点画一条标记为0的弧。
={q2,q2,
因为δ({q3},q3}, 所以,从标记为[q3]的顶点画一条到自身的
标记为0的弧
q
。0,q
此时
2,
,可得图
1)
3q-09,
(f)。
q0,
图39(增加在[q2,状态下的移动
-f) q0,q3]
注意到q3 是图39所示的NFA 的终止状态,所以,在图3中,状态[和[
q2,是等价的DFA 的终止状态。用双圈将它们标出,从而得到图3-11 。
f) q0,q3]
--9(q1,q0,
q3]
图3-11
图3-9所示NFA
的等价DFA
3.带空移动的有穷状态自动机
4
1.
知识点
(1)允许ε-NFA 在某一状态下不读入字符———不移动读头,而只改变状态。
(NFA 中,ε),)。所以,^ 与δ。
2)在ε^(^(需要严格区分δ
q,q,q,q,
-δε)≠δ(δa)≠δ(
a
(3)在εNFA 中,
(
^ 与
δ
需要分别进行扩展。
4)NFA 是ε-NFA 的特例。
(NFA,-NFA 是等价的, 统称它们为FA 。
-
δ
5)由于DFA,ε所以,
56
形式语言与自动机理论教学参考书(第4版)
2.
主要内容解读
定义39
带空移动的不确定的有穷状态自动机(non-deterministicfiniteautomatonwith
ε-vs,-
M
是一个五元组:
Q,δ,F)
moeεNFA)
其中,
M
=(Σ,q0,
Q,q0,
F
的意义同DFA 。
ε})→
2
Σ,
δ———状态转移函数,又称为状态转换函数或者移动函数,δ:Q×(Σ∪{
Q
。
对.(a)∈Q×Σ,q,={p2,…,} 可以有
q,δ(a)p1,pm
表示
M
在状态
q
读入字符a,
选择地将状态变成p1,p2,…, 或者pm
,并将读头向右移动一个带方格而指向输入
字符串的下一个字符。
对.q∈Q,δ(q,ε)={p1,p2,…,pm
}表示
M
在状态
q
不读入任何字符,可以有选
择地将状态变成p1,或者pm
p2,…, 。
或者
p2,…, 。也可以称为
M
在状态
q
做一个空移动(
ε
移动), 并且有选择地将状态变成p1,或者pm
^:,
同样地,将
δ
扩充为δQ×Σ*→2Q
。对任意q∈Q,w∈Σ* a∈Σ:
(1)εCLOSURE(={p|从
q
到
p
有一条标记为
ε
的路}。
-q)
(2)ε-P)=∪-p)。
CLOSURE(εCLOSURE(
p∈
P
(^()。
3)δε)εCLOSURE(
q,=-
q
(^(
{
P)。
^(w), 使得
p
∈δ(a)
}
4)δq,wa)=ε-CLOSURE(
P=
p|.
r
∈δq,r,
=
∪δ(a)
r,
^(w)
r∈δq,
进一步扩展δ:
Q
。对任意(P,
Q
×Σ:
2Q
×Σ→2a)∈
2
(P,=(a)
。
5)δ(a)∪q,
q∈
P
^:
Q
×Σ*
Q
×Σ*
再进一步扩展
δ
2→2Q
。对任意(P,w)∈2:
^(^
(
(6)δP,w)=∪δq,w)。
q∈
P
定义310
设
M
^
Q(q,
0,
δ,是一个
则称
εM
^(
不接受
x
, ^(
=(Σ,q0,F) -NFA 。对于.x∈Σ* 如果δx)∩F≠.,
q0,
则称
x
被
M
接受;如果δx)∩F=., 。
L(M)x|且δx)∩F≠.
}
称为由
M
接受(识别)的语言。
={x∈Σ* q0,
3-
2
ε-NFA 与NFA 等价
。
证明要点
:
(
1)等价构造
。
设ε-Q,δ1,F)
。
NFAM1=(Σ,q0,
取NFAM2=(Q,δ2,F2)。其中
,
Σ,q0,
有穷状态自动机
第
F∪{如果F∩εCLOSURE(
q0} -q0)≠.
3
F2=
F
如果F∩ε-q0)=.
章
使δ2(a)δq,)
。
关键点
:
对.(q,a)∈Q×Σ, q,=^1(
a
CLOSURE(
57
①让NFA 用非空移动去代替ε-NFA 的含有一系列移动,其中含若干个空移动和相应的
一个非空移动。
-q0)≠. 的情况,
②对F∩εCLOSURE(要进行特殊处理。
(施归纳于|证明δ2(x)δq0,)。
2)对.x∈Σ+, x|, q0,=^1(
x
(3)证明对.x∈Σ+,δ2(x)∩F2≠..δq0,
(M1)
q0,
M2)。
^1(x)∩F≠.
。
4)证明ε∈L(.ε∈L(
5
FA
是正则语言的识别器
3.
3.1
FA
与右线性文法
5.
1.
知识点
(实际上可以与一个“ FA 处理该句子的过程相对
1)右线性文法推导句子的过程, 适当的”
应。这个对应的关键是右线性文法的语法变量与FA 状态的对应。
(
2)FA 接受的语言是RL 。
(不需要考虑与该DFA 中的陷阱状态直接
3)构造与所给的DFA 等价的右线性文法时,
相关的产生式。
(
4)RL 可以由FA 接受。
(5)当构造右线性文法对应的FA 时,构造出来的一般是NFA,并且需要增加一个终止
状态。
(6)定理3-3给出如何根据DFA 构造右线性文法。从相应的证明可以知道,这个构造方
法对NFA 也是有效的。定理3-4给出了如何根据正则文法构造等价的NFA 。
2.
主要内容解读
3-
3
FA 接受的语言是正则语言
。
证明要点
:
由于曾经将正则语言定义为正则文法产生的语言,所以要证明此定理,只要证明对于任意
给定的
(
DFA,存在等价的正则文法就可以了。
1)构造。
构造的基本思想是让正则文法的派生对应DFA 的移动。
设DFAM
=(Σ,q0,F)。
Q,δ,
取右线性文法G=(Q,P,其中,=q→aδ(a)p}∪{δ(a)
Σ,q0),
P
{p|q,=q→a|q,=
p∈F}。满足L(G)=L(M)-{ε}。
q→a|q,=p∈F}
这里的关键问题是对{δ(a)所表示的产生式的理解,并且在实际的构造
58
形式语言与自动机理论教学参考书(第4版)
过程中不要被忽略掉。
ε}。
(2)证明L(G)=L(M)-
{
对于a1a2…an-1an
∈Σ+,有如下等价关系式
:
+
q2,…,1,
q0.a1a2…n-aq1,q2→a1n-n-
n
∈P
a1n
.q0→a1q1→a2n-n-qq1→a
.δ(q0,a1)q1,q1,=q2,…,q2,n-=n-δ(n-a)=
n
,且q
=δ(a2)δ(n-a1)q1,q1,nqn
∈
F
.δ(a1a2…1a)=
n
∈F
q0,n-nq
.a1a2…n-1a∈L(M)
(5和定理2-6考虑
ε
句子的问题。n(a) 定理2(a)
3)根据
例3-9不仅给出了定理3-3中所给出的构造方法的具体应用,而且这个例子还表明,在构
造所给的DFA 的等价RG 时,不需要考虑与该DFA 中的陷阱状态直接相关的产生式———因
为陷阱状态对应的语法变量是“无用符号”。所以,应该在将DFA 转换成RG 之前,先将所有
陷阱状态删除。另外,不可达状态对应的变量将不可能出现在相应文法的任何句型中,所以它
们对应的产生式也是无用的,因此,也应该事先删除所有的不可达状态。有关“无用符号”将在
2节中具体讨论
。
3-
4
正则语言可以由FA 接受
。
证明要点
:
6.
(
1)构造
。
基本思想是让FA 模拟RG 的派生
。
设右线性文法G=(T,S), 且ε.L(G)
。
V,P,
取FAM
=(T,S,{Z.V。对.
(
V∪{Z},δ,Z}),a,A)∈T×V,
a){B|A→aB∈P}∪{Z}A→a∈Pδ(A,={B|A→aB∈P} A→a.
P
在此用B∈δ(A)
B
对应, a,与产生式A→
a
对应。
a,与产生式A→a用Z∈δ(A)
(
M
)=G)。
2)证明L(L(
首先,对于a1a2…an-1an
∈T+
:
+
a1a2…an-1an
∈L(G).S.a1a2…an-1an
.S.a1A1.a1a2A2.….a1a2…an-1An-1.a1a2…an-1an
.S→a1A1,A1→a2A2,…,An-2→an-1An-1,An-1→an
∈
P
A2∈δ(a2),…,Z∈δ(
.A1∈δ(S,a1),A1,1∈δ(2,1),1,)
An-An-an-An-an
S,)
.Z∈δ(a1a2…an-1an
.a1a2…an-
n
∈L(M)
其次,根据定理2-充说明ε∈L(G)的情况
。6(1) 补(a)
3-
1
FA 与正则文法等价
。
这个推论是作为对定理3-3和定理3-4的总结
。
3.2
FA
与左线性文法
5.
1.
知识点
(
1)将左线性文法对句子进行归约的过程与FA 处理该句子的过程相对应。这个对应总
有穷状态自动机
第
体上可以通过语法变量与状态的对应表现出来。
3
(2)由于FA 与左线性文法等价,所以左线性文法也是RL 的一种描述,故将左线性文法
章
和右线性文法统称为RG 是合理的。
(也不需要考虑该DFA 中的陷阱状态和
3)在构造与给定的DFA 等价的左线性文法时,
不可达状态直接相关的产生式。
(
59
4)根据DFA 构造左线性文法
。
(
5)根据DFA 构造RG 的方法也可以用于根据NFA 构造RG 。
(6)当构造左线性文法对应的FA 时,一般构造出来的是NFA,并且需要增加一个开始状
态,文法的开始符号对应的状态为终止状态。
(
7)根据左线性文法构造FA 的方法。
2.
主要内容解读
3-
5
左线性文法与FA 等价
。
证明要点
:
(
1)证明文法中的归约与FA 中的移动可以相互模拟
。
(
2)根据DFA 构造左线性文法的方法。
方法1:
①删除DFA 的陷阱状态和不可达状态(包括与之相关的弧)。
②在图中加一个识别状态Z。
③“复制”一条原来到达终止状态的弧,使它从原来的起点出发,到达新添加的识别状
态Z。
④如果δ(a)B, a
A,=则有产生式B→A。
⑤如果δ(A,=B, 则有产生式B→a。
a)且
A
是开始状态
,
⑥
Z
为文法的开始符号。如果开始状态还是终止状态,则有产生式Z→ε
。
方法2:
①删除DFA 的陷阱状态和不可达状态(包括与之相关的弧)。
②如果δ(a)B,则B→A。
A,=
③如果δ(A,=B, 则有产生式B→a开始(a)
a)且
A
是状态,。
④如果δ(A,=且
B
是终止状态,则有产生式Z→Aa。
a)B,
⑤如果δ(a)A, 则有产生式Z→a
A,=且
A
既是开始状态又是终止状态,
。
⑥
Z
为文法的开始符号。如果开始状态还是终止状态,则有产生式Z→ε
。
(
3)根据左线性文法构造FA 的方法。
①增加状态
Z
为开始状态。
②如果A→B则δ(a)=A
。
a∈P
则
,
δ(
Ba,
)A,ε}
。
③如果A→a∈P, Z,=a∈Σ∪{
④文法的开始符号对应的状态为FA 的终止状态。
有了本节的结论以及给出的等价转换方法,对于一个给定的RL,可以用自己感觉比较方
便的方法构造一个描述,然后再将其转换成要求的形式。一般来讲,由于FA 的状态转移图比
较直观,所以,画出接受给定RL 的FA 的状态转移图是比较方便的,当画出状态转移图之后,
再将其转换成RG 。
60
形式语言与自动机理论教学参考书(第4版)
6
FA的一些变形
3.
本节内容可以只作为了解内容来阅读。
3.1
双向有穷状态自动机
6.
1.知识点
(1)2DFA允许读头前进、后退、不动。
(最终到达某个终止状
2)一个输入串被2DFAM
接受的充要条件是
M
从启动状态出发
,
态,并且读头处于输入串的最后一个字符的右侧
。
(
3)2DFA是正则语言的识别器。
头前进
(
、后退、不动。
可以像NFA那样, 并使读
4)2NFA在一个状态下读到一个符号, 选择进入某一个状态,
(
5)2NFA与DFA等价。
2.主要内容解读
定义31确定的双向有穷状态自动机(w-aeemnsiiieatao2DFA)
1
towydtriitcfntuomtn,
M
是一个五元组:
Q,δ,F)
Q,q0,
F
的意义同DFA 。
其中
δ,
—
Σ——
,
状态转移函数
q,
,又称为状态转换函数或者移动函数
M
=(Σ,q0,
,δ:Q×Σ→Q×{L,R,S}。对
.(a)∈Q×Σ,
如果δ(a)={L},表示
M
在状态
q
读入字符a,将状态变成p,并将读头向
左移动一个带方格而指向输入字符串中的前一个字符;
① q,p,
②如果δ(a)p,表示
M
在状态
q
读入字符a, 并将读头向
q,={R}, 将状态变成p,
右移动一个带方格而指向输入字符串的下一个字符;
如果δ(S},表示
M
在状态
q
读入字符a,将状态变成p,读头保持在
原位不动。
a)p,
关于FA的即时描述的定义对2DFA仍然有效
。
定义312
设MQ,δ,F)
M
接受的语
言
③ q,={
=(Σ,q0,为一个2DFA,
L(M)x|q0x|*
p
且p∈F}
3-
6
2DFA与FA等价。
={
x
证明要点
:
使用穿越序列。具体参考JohnE.Hopcroft,JefreyD.Ulman撰写的Intdctionto
AttaThy,Lgges,dComputation,该书由Addison-WesleyPublishingC(u) (o) (r) ompany979(ma) (o) ohn(a) E(n) .HopcrofJefreyD.Ulma
于1(u) 年出版(e) 。(o) 或者(a) 参(n) 阅J(a) (u) (r) t,n合著,莫绍揆等翻译的《形式语
有穷状态自动机
第
言及其与自动机的关系》。
3
定义31不确定的双向有穷状态自动机(n,
3
two-waynondeterministicfiniteautomato
章
2NFA)
M
是一个五元组:
Q,δ,F)
其中,
M
=(Σ,q0,
Q,q0,
F
的意义同DFA 。
61
Σ,
δ——又称为状态转换函数或者移动函数,Q×Σ→2Q×{L,R,q,
—状态转移函数,
a)p2,
δ:S}。对.(
a)∈Q×Σ,δ(q,={(p1,D1),(D2),…,(pm
,Dm
)}表示
M
在状态
q
读入字
符a,可以有选择地将状态变成p1,同时按D1 实现读头的移动,或者将状态变成
p2 同时按D2 实现读头的移动;……;或者将状态变成pm
,同时按Dm
实现读头的移
动。其中,D1,Dm
∈{R,表示的意义与定义31
D2,…,L,S}, -中表示的意义相同。
3-
7
2NFA与FA等价。
3.2
带输出的FA
6.
1.知识点
(e机和Mey机为带输出的FA,与基本FA只输出是否接受输入串不同,这两个
机器将根据输入串输出更多的内容。
(e机对应处理输入串的过程中经过的每个状态,都有一个字符输出。
1)Mooral
2)Mor
(y机对应处理输入串的过程中的每一个移动,都有一个字符输出
。
3)Meal
(4)在约定的意义上,Moore机与Mealy机等价。
2.主要内容解读
定义314
Moore机是一个六元组:
Q,Δ,λ,
其中,
M
=(Σ,δ,q0)
Q,
δ
的意义同DFA 。
Σ,
q0,
Δ———输出字母表(outputalphabet)
。
λ——λ:λ(=
。
—Q→
Δ
为输出函数。对.q∈Q,q)
a
表示
M
在状态
q
时输出
a
显然,对于.a1a2…an-1an
∈Σ*,
M
的输出串
为
λ(λ(q0,λ(δ(a1),…δ((δ(q0,a2)…),)
)
q0)δ(a1))δ(q0,a2))λ(…δ(a1)a
n
设
δ(a1)q1,q1,=q2,…,q2,n-=n-δ(n-a)=n
q0,=δ(a2)δ(n-a1)q1,q1,nq
则
M
的输出可以简单表示为
λ(λ(λ(…λ()
这是一个长度为n+1的串。
q0)q1)q2)qn
定义315
Mealy机是一个六元组:
Q,Δ,λ,
M
=(Σ,δ,q0)
62
形式语言与自动机理论教学参考书(第4版)
其中
,
Q,
δ
的意义同DFA
。
Σ,
q0,
Δ———输出字母表。
λ——λ
符
:
a
时输出d。
q,λ(a)
d
表示
M
在状态
q
读入字
—Q×Σ→
Δ
为输出函数。对.(a)∈Q×Σ,q,=
对于.a1a2…an-an
∈Σ*,
M
的输出串为
a1),……a1),)
λ(q0,λ(δ(q0,a2)…),n
λ(q0,a1)(1) δ(a2)δ(δ(a
设
δ(δ(δ()
q0,=q1,=n-a1)q1,n-a=n
a1)q1,a2)q2,n-=n-q1,nq
则
M
的输出可表示成长度为
n
的串:
q2,…,δ(
λ(λ(a2)…λ(n-1,
)
q0,a1)q1,qan
定义316
设Moore机
M1=(Q1,Δ,λ1,
Σ,δ1,q01)
Mealy机
M2=(Q2,Δ,λ2,
Σ,δ2,q02)
对于.x∈Σ*,当下式成立时,称它们是等价的
。
x)λ1(
其中,x)和T2(分别表示M1 和M2 关于
x
的输出
。
T1(=q0)T2(x)
T1(x)
3-
8
More机与Mealy机等价
。
证明要点
:
Moore机处理输入
x
时每经过一个状态,就输出一个字符,使得输出字符和状态一一对
应。所以,它的输出的长度为|x|+1 。
Mealy机处理输入
x
时的每一个移动输出一个字符,使得输出字符和移动一一对应。所
以,它的输出长度为|x|。
无论是根据Moore机构造等价的Mealy机,还是根据Mealy机构造More机,可以让它们
具有相同的状态和相同的移动函数:Q1=Q2,=。对输入串x,无论是Moore机还是
δ1δ2
Mealy机,都将经过|x|+1个状态,这些状态分别构成两个相同的状态序列,除了它们各自的
最后一个状态对应相等之外,其他的状态都对应于相同的转移,所以,忽略More机在启动时
对应于启动状态的输出,令Moore机对应的状态的输出等于Mealy机做相应的到达此状态的
移动对应的输出就可以了。
3.小结
7
本章主要讨论正则语言的识别器———FA,包括DFA,NFA,-NFA 。讨论RG与FA的等
价性,并且简单介绍带输出的FA和双向FA 。
ε(1)FAM
是一个五元组,
M
=(Σ,q0,F),它可以用状态转移图表示。
Q,δ,
等价。
(2)
M
接受的语言为{x∈Σ* q,M1)M2)
,
x|且δ(x)∈F}。如果L(=L(则称M1 与M2
有穷状态自动机
(
3)FA的状态具有有穷存储功能。这一特性可以用来构造接受一个给定语言的FA 。
(4)NFA允许
M
在一个状态下读入一个字符时,有选择地进入某一个状态,对于.x∈
Σ*,如果δ(x)∩F≠., 如果δ(x)∩F=., 。
M
接
q0,则称
x
被
M
接受; q0,则称
M
不接受
x
受的语言L(M)x|且δ(x)∩F≠. }。
={x∈Σ* q0,
(NFA是在NFA的基础上,允许直接根据当前状态变换到新的状态而不考虑输入带5)ε-
δ(ε)p2,…,表示
M
在状态
q
不读入任何字符,
上的符号。对.q∈Q,q,={p1,pm
} 可以有选
择地将状态变成p1,p2,…,或者pm
。这称为
M
在状态
q
做一个空移动。
(6)NFA与DFA等价,ε-NFA与NFA等价,统称它们为FA 。
(7)根据需要,可以在FA中设置一种特殊的状态———陷阱状态。但是,不可达状态却应
该无条件地删除。
8)FA是正则语言的识别模型。分别按照对推导和归约的模拟,
文法、
(
左线性文法等价。
可以证明FA和右线性
(9)2DFA是FA的又一种变形,它不仅允许读头向前移动,还允许读头向后移动。通过
这种扩充,
2DFA仍然与FA等价。2DFA进一步扩展所得2NFA也与FA等价。
(e机和Meloe机根据状态决定输出字符,
10)Moray机是两种等价的带输出的FA 。MorMealy机根据移动决定输出字符。
3.典型习题解析
8
2.构造识别下列语言的DFA(给出相应DFA的形式描述或者画出它们的状态转移图)。
(0,+。
2){1}
解:本题的关键是保证接受的串的长度至少为1,相应的DFA如图3-18(a)所示。
图3-18(a) 题2(2)的DFA
3){1}
解:构造要点是,自动机启动并读入一个字符后,就将“精力”集中在考查是否出现00子
串上,一旦发现子串00,就进入陷阱状态。构造结果如图3-18(b)所示。
(x|x∈{0,+且
x
中不含形如00的子串}。
图3-18(b) 3)
题2(的DFA
(x|x∈{0,1}+ 且当把
x
看成二进制数时,
x
模5与3同余,要求当
x
为0时,7){
x
的首字符为1}。
|x|=1,且当x≠0时,
第
章
63
64
形式语言与自动机理论教学参考书(第4版)
解:构造要点如下。
①以0开头的串都不能被此DFA 接受,包括字符串0。所以,如果DFA 在启动状态读入
的符号为0,则直接进入陷阱状态。
②该DFA 共有7个状态:开始状态、陷阱状态、终止状态各一个,在相应的状态转移图
中,终止状态和其余4种状态构成最大的强连通子图。
③其余部分请参考主教材例3-5
。
(9){x∈{1}
x|0,+且
x
以0开头以1结尾}
。
解:构造要点如下
。
①启动时,只要考虑开始符号是否为0。
②以1开头的字符串都是不可接受的。
③在读入一个字符0之后,当读到1时,可将这个1先当成结尾的1,如果是,就停止并接
受;如果不是,就继续向前扫描。
④被接受串的长度至少为2
。
构造结果如图3-c)
18(所示。
图3-18() 题2(9)的DFA
c
(x|x∈{1}* 则它的长度为偶数; 则它的长
11){0,且如果
x
以1结尾, 如果
x
以0结尾,
度为奇数}。
解:构造要点如下。
1}
①语言根据句子长度的奇偶性对句子的结尾符号提出要求,因此,它将{0,+中的字符
串分成4个等价类,这4个等价类依次为:
[奇0]—x|x∈{1}+ 而且以0结尾}。
——{0,不仅长度为奇数
,
[奇1]—x|x∈{1}而且以1结尾}
。
——{0,+不仅长度为奇数
,
[偶0]—x|0,+不仅长度为偶数
,
——{x∈{1}而且以0结尾}
。
[偶1]—x|0,+不仅长度为偶数
,
——{x∈{1}而且以1结尾}。
这里直接用[奇0]、[奇1]、[偶0]、[偶1]分别标示这4个等价类对应的状态,这样理解起
来就比较方便。显然,[ 奇0]、[偶1]对应的状态为终止状态。
②
ε
不属于上述任何一个等价类,所以,它自己独立地构成一个等价类,而且它是语言的
句子,该等价类对应的状态为终止状态。可以用[表示此等价类及其对应的状态。
③Q={[ε],[ 奇0],[ 偶0],[
ε0]
,δ,[ε],[ 偶1]},
下面状态转移表表示。
奇1],[ 偶1]},{1},ε],{[奇0],[ 其中
δ
由
[ε] [奇0] [奇1] [偶0] [偶1]
0 [奇0] [偶0] [偶0] [奇0] [奇0]
1 [奇1] [偶1] [偶1] [奇1] [奇1]