编译原理词法分析有穷自动机课件.ppt

《编译原理词法分析有穷自动机课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、不确定的有穷自动机NFAM=(S，∑，δ，S0，F)03124aabba,ba,ba,bNFA的定义M=(S，∑，δ，S0，F)(1)S是有穷状态集合(2)∑是有穷字母表(3)δ是一个从S×∑*到S的子集的映射(4)S0S,是非空初态集(5)FS是一个终态集(可空)NFA的表示方式1).状态转换图2).转换函数3).矩阵表示(TransitionTable)1).状态转换图03124aabba,ba,ba,b初态结点标以“=>”或""终态结点标以双圈2).转换函数NFAM=({0,1,2,3,4},{a,b},δ,{0},{2,4},)δ(

2、0，a)={0,3}δ(2，b)={2}δ(0，b)={0,1}δ(3，a)={4}δ(1，b)={2}δ(4，a)={4}δ(2，a)={2}δ(4，b)={4}3).矩阵表示(TransitionTable)状态字符ab0{0,3}{0,1}1{}{2}2{2}{2}3{4}{}4{4}{4}用“=>”标明初态；否则第一行即是初态终态行在表的右端标以1，非终态标以000101=>简化的矩阵表示状态字符ab00,30,1122223444400101NFA作为一种识别机制如果t从初始状态出发,在自动机上运行,能够到达终态,则t可为NFA所识

3、别(接受、读出)若存在一条从初态结点到某一终态结点的道路，且这条路上的所有弧的标记符连接成的字符串等于t，则称t可为NFA所识别XYbaεε134ab2εbaεab56例证明t=baab可被下图所示自动机所识别t在自动机上运行寻找一条从初态到终态的道路023a1abbbaa,bε可为NFA识别δ(Q,ε)=QM的某些结点既是初态结点又是终态结点存在一条从某初态结点到某终态结点的ε道路SaSaBCbcεε一个NFA所定义的语言L(M)NFAM所能接受的符号串的全体,记为L(M)L(M)＝{t

4、δ(S0,t)∩FΦ,t∈∑*}XYbaεε134ab

5、2εbaεab56含有相继两个a或相继两个b的串023a1abbbaa,bExample有穷自动机等价的定义有穷自动机M和M',若L(M)=L(M'),则M和M'等价023a1abbbaa,bXYbaεε134ab2εbaεab56补充练习1.构造NFA,可以识别标识符l(l

6、d)*2.构造NFA,可以识别a,b,c组成的串,但是所含a的个数不超过1.(即可含一个a或不含a)3.构造NFA,可以识别a,b,c组成的串,串中只含一个a4.构造NFA,可以识别a,b,c组成的串,串中至少含一个a5.构造NFA,可以识别不以a开头,但以aa结尾的字符串

7、课堂练习-＝{a,b}，构造NFA，识别以a开头,并且以aa结尾的字符串集合