文档介绍：*《编译原理与技术》讲义*编译原理与技术词法分析(2)*《编译原理与技术》讲义*有限自动机有限自动机(FiniteAutomata-FA)是种更一般化的状态转换图。分为NFA和DFA。词法分析器自动生成:正规式NFA DFA词法程序非确定有限自动机确定的有限自动机*《编译原理与技术》讲义*非确定有限自动机-NFANFAMn是一个五元组Mn=(,S,S0,F,),其中:-有限字母表(输入符号集)S-有限状态集S0-非空初态集合,S0SF-终态集合,FS-状态转换函数,Sx*2S*《编译原理与技术》讲义*确定的有限自动机-DFADFAMd是一个五元组Md=(,S,S0,F,),其中: ,S,S0,F同NFA中的定义,而定义如下: :SxS,为一单值映射函数。*《编译原理与技术》讲义*有限自动机的表示1)状态转换图开始状态一般状态终态s(s,a)=ttas(s,)=tt*《编译原理与技术》讲义*有限自动机的表示2)状态转换矩阵(表)*状态(集)ab…Si{Sj}…Sj……(Si,a)={Sj}*《编译原理与技术》讲义*=(,S,S0,F,),其中: ={0,1},S={S0,S1,S2,S3,S4},F={S2,S4} (S0,0)={S0,S3}(S0,1)={S0,S1}(S1,0)=∅(S1,1)={S2}(S2,0)={S2}(S2,1)={S2}(S3,0)={S4}(S3,1)=∅(S4,0)={S4}(S4,1)={S4}*《编译原理与技术》讲义*:S0S3S10,1000,1110,1S2S4*《编译原理与技术》讲义*(表)如下:*状态(集)01S0{S0,S3}{S0,S1}S1∅{S2}S2{S2}{S2}S3{S4}∅S4{S4}{S4}*《编译原理与技术》讲义*(接受)的串是什么?S0S1S201FA识别(接受)串∈*,如果存在一个从FA的初态到某个终态的(状态)转换路径,该路径上所有标记的字符依次连接为。FAM所识别的语言L(M) L(M)={|M识别∈*}