第二章 形式语言与自动机理论基础(有限自动机)

《第二章 形式语言与自动机理论基础(有限自动机)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2.2有限自动机(DeterministicFiniteAutomata)一.DFA的定义二.DFA的三种表示三.DFA接受的语言2.2.1确定的有限自动机(DFA)一DFAM定义一个确定的有限自动机DFAM是一个五元组Ｍ＝（Σ，S，S0，Z，f）Σ是一个字母表，它的每个元素称为一个输入符号。S是一个有限状态集合。S0∈S，S0称为初始状态。Z是S的子集，称为终结状态集合。f是一个从S×Σ到S的单值映射f(ｑ，ａ)＝ｑ’（ｑ,ｑ’∈S，ａ∈Σ）表示当前状态为q,输入符号为a时，自动机将转换到下一个状态ｑ’，ｑ’称为ｑ的后继。

2、例设ＤＦＡ　Ｍ＝（｛ａ，ｂ｝，｛０，１，２，３｝，０，｛３｝，f）其中f（０，ａ）＝１，f（１，ａ）＝３f（２，ａ）＝１，f（３，ａ）＝３f（０，ｂ）＝２，f（１，ｂ）＝２f（２，ｂ）＝３，f（３，ｂ）＝３二ＤＦＡ的三种表示：（1）用转换函数（2）转移矩阵（3）状态转换图所谓确定的状态机，其确定性表现在状态转移函数是单值函数！（1）用转换函数f（０，ａ）＝１，f（１，ａ）＝３f（２，ａ）＝１，f（３，ａ）＝３f（０，ｂ）＝２，f（１，ｂ）＝２f（２，ｂ）＝３，f（３，ｂ）＝３（2）转移矩阵横坐标纵坐标0132aaaabbbb3

3、（3）状态转换图结点表示状态，箭弧标记为字母表中的字母输入字符状态ab012132213333终结状态如何表示？三DFAM接受的语言(字符串集)如果对所有ｗ∈Σ*，以下述方式递归地扩充f的定义f（ｑ，ε）＝ｑf(ｑ，ｗａ）＝f(f(ｑ，w），ａ）对于上例中的DFAM和w=baa，f(0，baa）=f(2,aa）=f(1,a）=30132aaaabbbb30b2a1a33该DFAM能够识别字符串baa从状态转换图看，从初态出发，沿任一条路径到达终结状态，这条路径上的弧上的标记符号连接起来构成的符号串为DFAM所识别。DFAM所

4、能识别的符号串的全体记为L(M)，称为DFAM所识别的语言。Ｌ（Ｍ）＝｛ｗ｜ｗ∈Σ*，若存在ｑ∈Z，使f（ｑ０，ｗ）＝ｑ｝2.2.2非确定的有限自动机（NFA）NondeterministicFiniteAutomata一.NFAm的定义二.FA的等价定理三.具有-转移的NFA构造DFA的算法非确定有限自动机M是一个五元组M＝（Σ，S，S０，Z，f）其中Σ，S，Z的意义和DFA的定义一样，其中S０表示初始状态集，f是一个从S×(Σ∪{})到S的子集的映射，即f：S×(Σ∪{})２S，其中２S是S的幂集，即S中所有子集组

5、成的集合。一NFA的形式定义:确定的和非确定的有限自动机之间的重要区别是1、状态转换函数是一个多值映射；反映在状态转换图上即对同一弧标记到达的状态结点不惟一。2、NFA初态集，而DFA是一个唯一的状态.NFA存在弧标记0132ababbab3类似ＤFA，NFAm可用状态转换图表示，如果f(ｑ，ａ）={ｑ1，ｑ2...，ｑk}，则从q出发分别向ｑ1，ｑ2...，ｑk各画出一条标记为a的箭弧(非确定的含义)。同理可定义NFAm所识别（接受）的语言。Σ*中所有可能被NFAm所识别的符号串的集合记为L(M)。NFAM’所识别的语言

6、为:L(M’)={α

7、f(q0,α)=qq∈Z}定理对任何一个NFAM，都存在一个DFAM’，使L(M’)=L(M)构造方法：用M’的一个状态对应M的多个状态，用这种方法，能从一个NFAM构造一个等价的DFAM’，称作子集构造法。二.FA的等价定理NFAM=(S,,f,S0,Z)等价的DFAM’=(S’,’,f’,S0’,Z’)S’=2S(由NFAM的状态集S的所有子集组成)Z’={K

8、K∈S’且K≤Z≠}（Z’是由至少包含Z中一个状态S的所有子集组成）S0’={S0}’=f’(K,a)=P,其中K,P∈S’且P=

9、{p

10、p∈f(q,a),q∈k}DFAM’的f’:f’({k1,k2,…ki},a)={p1,p2,…pi}当且仅当NFAM的f:f({k1,k2,…ki},a)={p1,p2,…pi}证明（略P30）定义集合I的ε-闭包：令I是一个状态集的子集，定义ε-closure（I）为：1）若s∈I，则s∈ε-closure（I）；2）若s∈I，则从s出发经过任意条ε弧能够到达的任何状态都属于ε-closure（I）。状态集ε-closure（I）称为I的ε-闭包通过例子来说明状态子集的ε-闭包的构造方法三、具有-转移的NFA构造等

11、价DFA的方法例：如图所示的状态转换图：令I={1}，求ε-closure（I）=？156432aεεaε根据定义：ε-closure（I）={1，3，5}构造等价DFA算法若t1是NFA的初态，DFA的初态A=—closure({t1})。对NFA中每一个箭弧标记m，计算