第二章 词法分析 .pptVIP

3.3.2确定有限自动机（DFA）一个确定有限自动机（DFA）M是一个五元式：M＝(S,∑,δ,s0,F)，其中1、S是一个有限集，它的每个元素称为一个状态2、∑是一个有穷字母表，它的每个元素称为一个输入字符3、δ是一个从S×∑至S的单值部分映射。δ(s,a)=s′意味着：当现行状态为、输入字符为a时，将转换到下一状态s′。我们称s′为s的一个后继状态。4、s0∈S是唯一的初态5、FS是一个终态集（可空）。第29页，共54页，星期日，2025年，2月5日显然，一个DFA可用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示δ(s,a)的值。这个矩阵称为状态转换矩阵。例3-12：有DFAM=({0,1,2,3},{a,b},δ,0,{3})其中δ为:δ(0,a)=1δ(0,b)=2δ(1,a)=3δ(1,b)=2δ(2,a)=1δ(2,b)=3δ(3,a)=3δ(3,b)=3状态ab012132213333相应的状态转换矩阵如下表：第30页，共54页，星期日，2025年，2月5日一个DFA也可用一张（确定的）状态转换图来表示。假定DFAM含有m个状态和n个输入字符，那么，这个状态转换图含有m个状态结点，每个结点顶多有n条箭弧射出和别的结点相连接，整张图含有一个初态结点和若干个（可以为0）终态结点。301图3.5状态转换图2aaaabbb状态ab012132213333如下表所示的状态转换矩阵对应的状态转换图如右图：第31页，共54页，星期日，2025年，2月5日3012aaabbb上图所示的状态转换图的S、∑及∑*如下：S={0,1,2,3}∑={a,b}∑*={α|α为ε，或者α为a、b的任意组合}从初态0到终态3有如图所示的通路，箭弧上到标记符连接起来的字aa属于∑*，所以右图所示的DFA可以识别字aa。同理：从初态0到终态3还有如图所示的通路，箭弧上到标记符连接起来的字bba属于∑*，所以右图所示的DFA可以识别字bba。a第32页，共54页，星期日，2025年，2月5日例3-13：科学表示法中数字常量的正则表达式对应的DFA：digitdigitnat对应的DFA如下图digit=[0-9]nat=digit+signedNat=(+|-)?natnumber=signedNat(“·”nat)？signedNat对应的DFA如下图加上可选的小数部分，数字常量的正则表达式number=signedNat(“·”nat)？对应的DFA如下图：+digitdigitdigit-+digitdigitdigit-digitdigit?第33页，共54页，星期日，2025年，2月5日abbb接受与正则式ab+|ab*|b*相同的语言的DFA如下所示：第34页，共54页，星期日，2025年，2月5日例3-14：串中只有一个b被如下所示的DFA接受：bnotbnotb例3-15：包含最多一个b的串被如下所示的DFA接受：bnotbnotb注意二者之间的区别第35页，共54页，星期日，2025年，2月5日定理：如果一个DFAM的输入字母表为∑，则我们也称M是∑上的一个DFA。可以证明:∑上的一个字集V∑*是正规的，当且仅当存在∑上的DFAM，使得V=L(M)。DFA的确定性表现在映射δ：S×∑→S是一个单值函数。即：对于任何状态s∈S和输入符号a∈∑，δ(s,a)唯一确定了一个状态。从转换图角度，我们也可以得到答案。如果允许是一个多值函数，我们就得到下一节要讲到的非确定自动机的概念。第36页，共54页，星期日，2025年，2月5日3.3.3非确定有限自动机（NFA）一个非确定有限自动机（NFA）M是一个五元式：M＝(S,∑,δ,S0,F)，其中1、S是一个有限集，它的每个元素称为一个状态2、∑是一个有穷字母表，它的每个元素称为一个输入字符3、δ是一个从S×∑*至S的子