2.2有限自动机一DFAM定义一个确定的有限自动机DFAM是一个五元组Ｍ＝（Σ，S，S0，Z，f）例设ＤＦＡＭ＝（｛ａ，ｂ｝，｛０，１，２，３｝，０，｛３｝，f）其中f（０，ａ）＝１，f（１，ａ）＝３f（２，ａ）＝１，f（３，ａ）＝３f（０，ｂ）＝２，f（１，ｂ）＝２f（２，ｂ）＝３，f（３，ｂ）＝３所谓确定的状态机，其确定性表现在状态转移函数是单值函数！（2）转移矩阵0三DFAM接受的语言(字符串集)如果对所有ｗ∈Σ*，以下述方式递归地扩充f的定义f（ｑ，ε）＝ｑf(ｑ，ｗａ）＝f(f(ｑ，w），ａ）对于上例中的DFAM和w=baa，f(0，baa）=f(2,aa）=f(1,a）=3从状态转换图看，从初态出发，沿任一条路径到达终结状态，这条路径上的弧上的标记符号连接起来构成的符号串为DFAM所识别。DFAM所能识别的符号串的全体记为L(M)，称为DFAM所识别的语言。2.2.2非确定的有限自动机（NFA）NondeterministicFiniteAutomata非确定有限自动机M是一个五元组M＝（Σ，S，S０，Z，f）其中Σ，S，Z的意义和DFA的定义一样，其中S０表示初始状态集，f是一个从S×(Σ∪{})到S的子集的映射，即f：S×(Σ∪{})２S，其中２S是S的幂集，即S中所有子集组成的集合。0类似ＤFA，NFAm可用状态转换图表示，如果f(ｑ，ａ）={ｑ1，ｑ2...，ｑk}，则从q出发分别向ｑ1，ｑ2...，ｑk各画出一条标记为a的箭弧(非确定的含义)。同理可定义NFAm所识别（接受）的语言。Σ*中所有可能被NFAm所识别的符号串的集合记为L(M)。定理对任何一个NFAM，都存在一个DFAM’，使L(M’)=L(M)构造方法：用M’的一个状态对应M的多个状态，用这种方法，能从一个NFAM构造一个等价的DFAM’，称作子集构造法。—closure(f(A，a))的含义NFA中从集合A中的状态出发，先经若干箭弧，接着经标记为a的箭弧到达的状态集合的—closure。states等价的DFA的状态转换图例：有NFAM’A=ε-closure({1})={1,4}DFAM的状态图：具有-转移的NFA构造等价DFA的方法例NFAM=(0,1,q0,q1,q0,{q1,f),其中f(q0,0)=q0,q1,f(q0,1)=q1f(q1,0)=f(q1,1)=q0,q12.2.3确定有限自动机的化简区分终态与非终态NFA2.3正规式（正规表达式）与有限自动机2.3.1正规表达式与正规集正规表达式的递归定义规定“*”，“连接”，“”运算左结合，优先级由高到低简化正规式(a)((b)*(c))等价于ab*c例：=A,B,…,Z,a,b,…,z,0,1,…,9正规式1：AB...Zab...z语言1：L(A)∪L(B)…∪L(Z)∪L(a)∪L(b)...∪L(z)=A,B,…,Z,a,b,…,z正规式2：01...9语言2：L(0)∪L(1)∪...∪L(9)=0,1,…,9例=a,b(a)abL(a)∪L(b)=a,b(b)(ab)(ab)(L(a)∪L(b))(L(a)∪L(b))=aa,ab,ba,bb(c)a*(L(a))*=,a,aa,aaa,aaaa,…(d)(ab)*(L(a)∪L(b))*={,a,b,aa,ab,ba,bb,aaa,...(e)aa*b符号串a和包括零个或多于零个a后跟一个b构成的所有符号串思考：C++语言的标识符?正规式：(AB...Zab...z_)((AB...Zab...z)_(01..9))*语言：A,B,…,Z,a,b,…,z,_(A,B,…,Z,a,b,…,z,_,0,1,…,9)*正规表达式的代数性质描述单词符号的结构，是进行词法分析程序设计的第一步,在表示的基础上如何做进一步的工作？2.3.2正规式与有限自动机关系图：对于上任一正规表达式r，一定能构造一个NFAm，使得L(r)=L(m)。首先把转换图的概念拓广，每条弧上可以用一个正规式标记，对NFAm构造一个广义的转换图。其中只有开始状态S和终止状态Z，连接S和Z的有向弧上是正规式R，然后按照下面的替换规则对正规式不断进行分解，不断加入状态结点和箭弧，直到转换图上的所有弧标记都是上的元素或为止。a设={x,y},上的正规式R=xy*(xy|yx)x*，构造一个NFAM，使L(M)=L(R).对于上任一NFAm，能构造上一个正规表达式r