资源描述：
《词法分析与有限状态自动机课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2021/8/5华东师大计算机科学技术系1有限状态自动机3.1.1基本概念FA的非形式描述有限状态自动机由3部分组成：⑴一根输入带：输入带可以理解成由一系列带块组成，每个带块上只含有一个输入符号（终结符号），其全体构成集合VT，特殊符号“”表示输入符号串的结束，VT。⑵一个输入头：初始时，输入头指向第一个带块（即指向输入带最左端的带块），输入头每次将输入头下方带块上的输入符号读入，然后输入头向右移动一个带块。2021/8/5华东师大计算机科学技术系2基本概念⑶一个有限状态控制器：有限状态控制器所能处于的
2、状态的全体组成状态集合Q，Q中有若干特殊状态：一个初始状态q0和若干最终状态qf。开始时有限状态控制器处于初始状态，以后有限状态控制器所处状态由状态转换函数决定。2021/8/5华东师大计算机科学技术系3基本概念例1令VT={0,1,2,3}Q={S,A,B}2030S是初态用‘-’表示A是终态用‘+’表示有向弧表示转换2021/8/5华东师大计算机科学技术系4FA的工作过程初始时，FA处于初态，输入头指向第一个输入符，随着带上符号的读入，FA从一个状态转向另一个状态。若遇到如下情况，FA结束工作：输入头
3、指向‘’、FA处于终态。称输入串被FA接受。（如2030）输入头指向‘’、FA不在终态。称输入串不被FA接受。（如203）FA无法转换。称输入串不被FA接受。（如1031）2021/8/5华东师大计算机科学技术系5FA的形式描述定义1：有限状态自动机M是一个五元组：M＝(VT,Q,,q0,Qf)，其中：VT：有限非空终结符集合Q：有限非空状态集合：从Q×VT到Q的幂集2Q上的状态转换函数q0：初始状态，q0QQf：最终状态集，QfQ
4、Qf
5、≥12021/8/5华东师大计算机科学技术系6FA的
6、形式描述对q,q1QaVT(q,a)={q1}的含义为：当前状态为q，若输入头所指符号为a，则转向下一状态q1，输入头右移。∵是Q×VT2Q上的一个单射一般地(q,a)={q1,q2,……qn}qiQi=1,2,…n因此称FAM为不确定的FA，记为NFA。若映射是Q×VTQ，即对任何qQ，aiVT，(q,ai)至多只有一个元素q’，称FAM是确定性的FA，记为DFA。2021/8/5华东师大计算机科学技术系7FA的形式描述对FA的拓展Q0Q
7、Q0
8、≥1即初态可以是一个集合：从Q×VT
9、*到2Q上的单值映射，即输入符可以是一个串，包括称M为一个传递图或转换系统或NFA。例1：M1＝(VT,Q,,q0,F)VT={a,b},Q={q0,q1,q2}F={q2}:(q0,a)=q1(q0,b)=q2(q1,a)=q1(q1,b)=q1(q2,a)=q2(q2,b)=q1M1是一个DFA。2021/8/5华东师大计算机科学技术系8FA的表示3.1.2状态转换图和状态转换表状态转换图：qQ若q，q’Q，aVT，且q’(q,a)，初态用‘－’标记、终态用‘+’标记qqq’
10、a2021/8/5华东师大计算机科学技术系9状态转换图例2：例1的DFAM1可表示为：—＋q0q2q1abbaa,b2021/8/5华东师大计算机科学技术系10状态转换表状态转换表（矩阵）表的列对应输入符号及特殊符号‘’，行和M的状态q相对应。状态转换表的qi行aj列中填以(qi,aj)中的状态。表的第一行和M的初始状态q0相对应；‘’这一列和最终状态qf行的元素标以A，以表示该状态是最终状态。2021/8/5华东师大计算机科学技术系11状态转换表例3：例1的DFAM1可表示为：Mabq0q1q2q1
11、q1q1q2q2q1A2021/8/5华东师大计算机科学技术系12示例例4：设计一个接受以a为头符号和尾符号，中间可出现任意多个a,b的符号串的FAM。解：令：VT={a,b}Q={q0,q1,q2}a—＋q0q2q1aaa,baM是NFA2021/8/5华东师大计算机科学技术系13FA识别的语言格局FAM的一个格局是二元组（q,w)qQ，wVT*动作对q’(q,a)则FAM的动作记为：(q,aw)(q’,w)aVTwVT*对wVT*，q0是初态，称w被FAM所接受，表示为：(q0,w)
12、(qf,)qfF*2021/8/5华东师大计算机科学技术系14FA识别的语言定义2：设M是一个FA，wVT*若：(q0,w)(qf,)qfFq0是初态称w是M的一个句子。M句子的全体称为M的语言，记为：L(M)={w
13、(q0,w)(qf,),wVT*}例5：对例4的NFAM，输入串abba有：(q0,abba)(q1,bba)(q1,ba)(q1,a)(q2,)∵q2
