第三章有穷自动机.ppt

第三章有穷自动机
第1页，本讲稿共74页
§ 有穷自动机的形式定义
有穷状态自动机(Finite-state Automata 或简称FA)在识别功能上与正规文法类等价，而且也等价于一个特殊类型的语言产生器——正规表达式101)= ((S,1),1101)= (A,1101)= ((A,1),101)= (S,101)= ((S,1),01)= (A,01)= ((A,0),1)= (C,1)= B(拒绝)
第12页，本讲稿共74页
所有为自动机M所能接受的串组成一个集合，称这个集合为自动机M所能接受的语言，用L(M)表示：
L(M)={ t | f(S,t)Z，t*}
对于任何两个有穷自动机M和M’，如果L(M)=L(M’)，则称M与M’是等价的。
第13页，本讲稿共74页
非确定有穷自动机
NFA定义
一个不确定的有穷自动机NFA M’是一个五元组：
M’=(K, ,f,S,Z)
一个含有m个状态和n个输入字符的NFA可表示为一张状态转换图，该图含有m个状态结，每个结可射出若干条 箭弧与别的结点相连接，每条弧用*中的一个字（不一定要不同的字，且可以为空字）作标记（称输入字），整个图至少含有一个初态结以及若干个终态结。
第14页，本讲稿共74页
NFA与DFA的区别
NFA有一个开始状态集，而DFA只有一个开始状态。
NFA的映射是QQ的子集，是一个多值映射，而DFA的映射是QQ，是一个单值映射。
DFA是NFA的特例，对于每个NFA M，存在一个DFA M’，使得L(M)=L(M’)。
第15页，本讲稿共74页
对于*中的任何一个串t，如果存在一条从某一初态结到某一终态结的道路，且这条道路上的所有弧的标记依序连接成的串等于t，则称t可为NFA M所识别（读出或接受）。
若M的某些结既是初态结，又是终态结，或者存在一条从某个初态结到某个终态结的道路，则空字可为M所接受。
第16页，本讲稿共74页
例： NFA M=({0,1,2,3,4},{a,b},f,{0},{2,4})
f(0,a)={0,3} f(2,b)={2} f(0,b)={0,1}
f(3,a)={4} f(1,b)={2} f(4,a)={4}
f(2,a)={2} f(4,b)={4}
可用状态图或矩阵表示：
0
3
4
1
2
a
a
b
b
a,b
a,b
a,b
第17页，本讲稿共74页
§ NFA到DFA的转换
通过下述步骤可将一个NFA转换成等价的DFA：
① 寻找并消除空移环路；
② 消除余下的空移；
③ 确定化。
第18页，本讲稿共74页
空移环路的寻找和消除
第19页，本讲稿共74页
消除空移
下面给出一个消除空移的算法。
给定从状态A到B的一个空移(即从状态A到B经由连线的一个转换，换言之，t(A,)={…，B，…})。置t(A,)=，对每个a和Q，如果Qt(B,a)，则将Q加到t(A,a)。如果A是开始状态，则将B也加入开始状态集。如果B是终止状态，则将A也加入终止状态集。
第20页，本讲稿共74页
利用状态转换表消除空移
利用FA的状态转换表，可以很容易地消除空移。这种方法的基本步骤是：
首先，找出直接经由一个空移到达某个终态的所有状态。每当找到这样一个状态，便将它标记为终态。
然后，考虑消除与未被标记为终态的那些状态相关的空移。对表中每一个具有射出ε连线的状态继续按上述方式处理，直到状态转换表不再变动为止。
最后从表中删除ε列和没有任何元素的空行，便得到一个不含空移的状态转换表。
第21页，本讲稿共74页
确定化——造表法
造表法是一种简单而有效的确定化方法。
定义：设NFA M=(Q, ∪{}, t, Q0, F)，假定I是M中状态集的一个子集，定义_closure(I)如下：
若qI，则q_closure(I)；
若q_closure(I)，q是由q出发经多条弧到达的状态，则q_closure(I)。
第22页，本讲稿共74页
定义：假定I是NFA M中状态集的一个子集，a，定义
Ia=_closure(J)
其中J是所有那些可从子集I中的任一状态出发，经过一条a连线(跳过a连线前的ε连线)而到达的状态(结)的全体。
造表法的具体步骤：
假定给定的NFA M中仅含两个符号a，b。可用如下方法将M确定化：采用造表的方式，该