形式语言与自动机 第三章 有穷状态自动机1

形式语言与自动机FormalLanguagesandAutomataTheory第三章有穷自动机第三章有穷状态自动机一、有穷状态自动机FA定义与表示二、确定的有穷自动机DFA三、非确定的有穷自动机NFA四、DFA和NFA的等价性五、带空移动的有穷自动机ε-NFA六、FA是正则语言的识别器七、FA的变形-带输出的FA第一次课第二次课语言的识别

方法1：根据G的定义，寻找一个派生，或归约

一、有穷状态自动机定义与表示自动机系统的结构及功能特征分析：

1、字母表：系统处理的所有字符串由字母表上的字符组成；2、控制器：系统每次从输入字符串读入一个字符，并根据当前状态和读入的字符，转入新的状态；新的状态和当前状态可以相同也可不同；为此，系统具有有穷个状态,并需要维护一个读指针。3、几个特殊状态：一个开始状态；系统从此开始处理句子；一些称之为终止状态或接受状态，系统从开始状态至此状态为止，读入字符构成的字符串是语言的一个句子；系统到达这些状态读入的全部字符串构成系统所能识别的语言。有穷状态自动机定义与表示有穷状态自动机装置的物理模型：

有穷状态自动机定义与表示有穷状态自动机装置的组成：

1、一个具有一系列方格的输入字符串的带子：方格中存放字符，字符从输入带左端开始存放，输入带右端无穷；

2、一个有穷状态控制器FSC：控制一个读头；每读入一个字符，读头右移一格，指向下一个待读入字符。有穷状态控制器FSC的基本工作过程：

控制器执行动作由三个节拍组成：⑴

读头读入当前指向的字符；⑵根据读入的字符和其自身当前状态，改变有穷状态控制器的状态；⑶

读头右移一格指向下一个字符。有穷状态自动机定义与表示

8有穷状态自动机定义与表示

δ(q0,0)=q1δ(q0,1)=q3

δ(q0,2)=q3

δ(q1,0)=q2δ(q1,1)=q3δ(q1,2)=q3

δ(q2,0)=q1δ(q2,1)=q3δ(q2,2)=q3

δ(q3,0)=q3δ(q3,1)=q3δ(q3,2)=q3

状态表表示法：状态图表示法：q0q3q1q2{1,2}{1,2}{1,2}00{0,1,2}0012状态说明q0q1q3q3开始状态q1q2q3q3q2q1q3q3终止状态q3q3q3q3有穷状态自动机定义与表示函数表示法：

有穷状态自动机定义与表示注：状态转移图中可能存在一些并行弧，其从同一节点出发，到达同一节点。11一个例子:

分析：目标是构造一个DFA，识别串x是否有连续的3个0作为结尾.状态0.目前已经读入了0个0，即xxxx1或1状态1.目前已经读入了1个0，即

xxxx10或0状态2.目前已经读入了2个0，即

xxxx100或00状态3.目前已经读入了3个0，即

xxxx1000或000

0001S1有穷状态自动机定义与表示关于FA的几个基本概念：1、基于字符串的状态转移函数δ’2、FA的瞬时（即时）描述3、FA状态对读入字符串的存储功能4、何谓FA识别一个句子或语言5、FA

的等价性

有穷状态自动机定义与表示（1）

定义3.1的补充定义：有穷状态自动机定义与表示读入空串读入非空串对于任意的q

∈Q,w∈∑

,a

∈∑，有：

δ’(q,wa)=δ(δ’(q,w),a) =δ(δ’(q,a1a2a3…an），

a) =δ(…δ(δ(q,a1),a2),…,an),a)

说明1：DFA从状态q出发处理字符串wa

的状态转移过程：有穷状态自动机定义与表示说明2：由于Q×∑是Q×∑*的真子集；对于任意输入字符a，有δ(q,a)=δ(q,εa) ε是单位元素 =δ(δ(q,ε),a)由补充定义第2条=δ(q,a)

由补充定义第1条有穷状态自动机定义与表示可见，状态转移函数δ’可以涵盖描述δ，因此，不必区分的使用δ和δ

，通常一般性地用δ代替δ

。定义3.3：设FAM=(Q,,,q0,F)，x,y∈∑*，δ(q0,x)=q

,

xqy称为M的一个瞬时描述（ID），表示： xy是M正在处理的一个字符串，其子串x引导M从q0

启动，到达状态q,

M的读头当前指向子串y的首字符。有穷状态自动机定义与表示（2）如果xqay是M一个瞬时描述,且（q,a）=p

，则有：

xqay

xapy

表示M在状态q时已处理完字符串x；当前读入的字符为a且转入状态p,然后将读头向右移动一格，指向字符串y的首字符。FAM的瞬时移动描述：有穷状态自动机定义与表示FAM的瞬时移动序列描述：

：M从已识别的字符串出发，经过n次移动，识别的字符串变为；亦即，存在n个ID构成序列：

,

1,2,…,n-1,，使得

1

….

n-1

。有穷状态自动机定义与表示例：

q0abc→

aq1bc

→…

→

abcq3ε注：所有移动都在M中进行时，可省去推导符中的M，分别记为：几个特殊的瞬时移动序列描述：

：M的ID从

出发，经过若干步（包含零步）移动，变成

。

：M的ID从

出发，经过至少一步移动，变成。

：n=0,=。

（M没有移动）有穷状态自动机定义与表示FAM瞬时移动序列描述实例：例：FAM识别输入串1010010001，产生一

个瞬时移动描述序列：有穷状态自动机定义与表示

有穷状态自动机定义与表示（3）定义3-4：设有限自动机FAM=<Q,∑,δ,q0,F>,对于

q∈Q，能引导FA从开始状态到达q的字符串集合set(q)={x|x∈∑*且δ(q0,x)=q

}定义为状态

q对字符串的存储能力。例：接受语言L={x000|x∈{0,1}*}∪{x001|x∈{0,1}*

}的FAM各状态的字符串存储能力如下： set(q0)={x|x∈∑*,x=ε或者x以1结尾但不以001结尾}; set(q1)={x|x∈∑*,x=0或者x以10结尾} set(q2)={x|x∈∑*,x=00或者x以100结尾} set(q3)={x|x∈∑*,x仅以000结尾} set(q4)={x|x∈∑*,x仅以001结尾}L={x000|x∈{0,1}*}∪{x001|x∈{0,1}*}

set(q0)={x|x∈∑*,x=ε或者x以1结尾但不以001结尾}; set(q1)={x|x∈∑*,x=0或者x以10结尾} set(q2)={x|x∈∑*,x=00或者x以100结尾} set(q3)={x|x∈∑*,x仅以000结尾} set(q4)={x|x∈∑*,x仅以001结尾}有穷状态自动机定义与表示说明：1、上述5个集合两两互不相交；5个集合的并正好构成M识别输入字母表{0，1}的克林闭包；亦即，这5个集合是关于{0,1}*的一个划分；2、此划分可由M上的一个等价关系RM确定，亦即，

x,y∈∑*，xRMy

q∈Q,x,y∈set(q)有穷状态自动机定义与表示（4）

定义3-6：

设M1，M2是FA。如果L（M1）=L（M2），则称M1与M2等价。有穷状态自动机定义与表示（5）第三章有穷状态自动机一、有穷状态自动机FA定义与表示二、确定的有穷自动机DFA三、非确定的有穷自动机NFA四、DFA和NFA的等价性五、带空移动的有穷自动机ε-NFA六、FA是正则语言的识别器七、FA的变形-带输出的FA定义3-7：

确定的有限自动机，记作

DFA，为一个五元组M=<Q,∑,δ,q0,F>，其中，Q，∑，q0，F的意义与FA定义相同；状态转移函数δ:Q×∑→Q

为单值映射函数，即，对q∈Q和a∈∑,δ(q,a)=p有唯一映射值；M在状态q下读入字符a，将状态q变成唯一状态p，读头向右移动一个方格，指向输入字符串的下一个字符。二、确定的有穷自动机DFA例1：构造一DFM，使它接受语言L={x000y|x,y∈{0,1}*}。语言句子结构特征分析：对于任给输入字符串x∈{0,1}*，DFAM需逐一检查x的每个字符，判断其中是否存在连续的000作为子串，有则接受x,然后，继续读完字符串剩余的后缀y。确定的有穷自动机DFAFA的主框架分析：q0：M的开始状态；

q1：M在q0

后读入一个0，其可能是子串000的第一个0，记住；q2：M在q1后又读入一个0，其可能是子串000的第二个0，记住；q3：M在q2后又读入一个0，发现了子串000，记住，此状态为终态。设计–补足FA所缺失的其它状态：δ(q0,0)=q1–

可能读到x第一个0；δ(q0,1)=q0–回始态重新检查；δ(q1,0)=q2–可能读到x第二个0；δ(q1,1)=q0-回始态重新检查；δ(q2,0)=q3–发现x的子串000；δ(q2,1)=q0-回始态重新检查；

δ(q3,0)=q3

，δ(q3,1)=q3----已到达终态，继续接受字符串的后缀。

确定的有穷自动机DFA定义控制器的有限状态：状态表状态图确定的有穷自动机DFADFA识别字符下面哪个是自动机可识别的字符？A.epsilonB.011C.100011D.1011ABCD011100所识别语言中同一长度的字符数这个自动机可接受的长度最小的字符是2，共有两个，01和10。记作N(2)=2.请问：A.N(13)=16B.N(13)=84C.N(12)=14D.N(12)=624ABCD011100解：DFM可定义为：M=（{q0,q1,q2,q3},{0,1},{δ(q0,0)=q1,δ(q1,0)=q2,

δ(q2,0)=q3,δ(q3,0)=q3,δ(q0,1)=q0,δ(q1,1)=q0,

δ(q2,1)=q0,δ(q3,1)=q3

},q0，

q3

）。例1：构造一DFM，使它接受语言L={x000y|x,y∈{0,1}*}。确定的有穷自动机DFA例2：构造一DFM，使其接受语言L={0n1m2k|n,m,k≧1

}。语言句子结构特征分析：0在最前，1在中间，2在最后，三者不可交叉出现；不可颠倒顺序；字符0、1、2的个数均不得少于1。确定的有穷自动机DFAFA的主框架分析：q0：M的开始状态；

q1：M在q0

后读到至少一个0，等待读入更多个0；q2：M在q1后读入至少一个1，等待读入更多个1；q3：M在q2后读入至少一个2，等待读入更多个1

，此状态为终态。确定的有穷自动机DFA求识别L={0n1m2k|n,m,k≧1

}的DFAM补足FA缺失部分：

-引入陷阱状态qt(自锁态)：系统一旦进入则无法离开的状态。设计要点：1、构造一个识别给定语言的DFA时，可先根据语言的主要特征，画出该FA的主体框架图，然后考虑相关细节问题。2、一旦DFA发现无法识别的语言句子，则进入陷阱状态

qt；引入陷阱状态可方便FA的构造。

确定的有穷自动机DFA确定的有穷自动机DFA

确定的有穷自动机DFA

注意：M的每个状态给出了语言的等价类，所有状态构成了语言上的一个划分～

分析：什么是这里的“有穷状态”？（或者等价类）确定的有穷自动机DFA

注意：M的每个状态给出了语言的等价类，所有状态构成了语言上的一个划分～

分析：什么是这里的“有穷状态”？（或者等价类）

这些等价类之间如何转换？（xxa意味着xa=2*x+a）确定的有穷自动机DFA

确定的有穷自动机DFA

分析：什么是这里的“有穷状态”？小结：1、有穷自动机FA的一般概念：

自动机定义–五元组：M=<Q,∑,δ,q0,F>

；自动机表示方法：函数法，状态表，状态图；FA的瞬时移动序列描述：xqay

xapy

及n次移动合成；FA每个状态对读入字符串均具有某种存储功能：set(q)；

能为FA接受的语言；FA的等价等。2、确定型有穷自动机DFA的定义及其构造：

定义：DFA的状态转移函数

δ唯一；

构造：首先，根据语言结构特征设计DFA主框架，然后，运用其它未明示的信息补足主框架设计；设计中可增设“陷阱状态”。第三章有穷状态自动机一、有穷状态自动机FA定义与表示二、确定的有穷自动机DFA三、非确定的有穷自动机NFA四、DFA和NFA的等价性五、带空移动的有穷自动机ε-NFA六、FA是正则语言的识别器七、FA的变形-带输出的FA例3：求接受语言L（M）={x|x∈

{0,1}*，且 x含有子串00或11}的FA。状态表状态图三、非确定有穷自动机NFA

3、此时的NFA程序应视为拥有“智能”，亦即，在一给定状态下，它可根据当前从输入字符串读入的字符自动到δ(q,a)的转移状态集合中选择进入一个正确的状态。非确定有穷自动机NFA非确定有穷自动机NFA

几个相关的基本概念：1、引入基于字符串的状态转移函数δ’；2、

NFA接受句子及语言的条件3、两个NFA的等价非确定有穷自动机NFA

非确定有穷自动机NFA

非确定有穷自动机NFA定义3-8的补充：状态转移函数δ扩展为δ

对于任意的q

∈Q,w∈∑

,a

∈∑，有：

δ’(q,wa)=δ(δ’(q,w),a) =δ(δ’(q,a1a2a3…an），

a) =δ(…δ(δ(q,a1),a2),…,an),a)

非确定有穷自动机NFA说明1：NFA从状态q出发处理字符串wa

状态转移过程：说明2：由于Q×∑是Q×∑*

的真子集；对于任意的q∈Q，a∈∑

，有δ(q，a)=δ’(q，εa) ε是单位元素

={p｜ヨr∈δ(q，ε)，使得p∈δ(r,a)}由定义第2条 ={p｜ヨr∈{q}，使得p∈δ(r,a)}

由定义第1条 ={p｜p∈

δ(q，a)}

q是r的唯一值 =δ(q，a)