石河子大学信息科学与技术学院编译原理课件第四章 词法分析.ppt

一个DFA也可用一张（确定的）状态转换图来表示。假定DFA M含有m个状态和n个输入字符，那么，这个状态转换图含有m个状态结点，每个结点顶多有n条箭弧射出和别的结点相连接，整张图含有一个初态结点和若干个（可以为0）终态结点。 3 0 1 图4.5 状态转换图 2 a a a a b b b 3 3 3 3 1 2 2 3 1 2 1 0 B a 状态 如下表所示的状态转换矩阵对应的状态转换图如右图： 3 0 1 2 a a a b b b 上图所示的状态转换图的S、∑及∑*如下： S = {0,1,2,3} ∑= {a,b} ∑*= {α| α为ε，或者α为a、b的任意组合} 从初态0到终态3有如图所示的通路，箭弧上到标记符连接起来的字aa属于∑*，所以右图所示的DFA可以识别字aa。 同理：从初态0到终态3还有如图所示的通路，箭弧上到标记符连接起来的字bba属于∑*，所以右图所示的DFA可以识别字bba。 a 例4-13：科学表示法中数字常量的正则表达式对应的DFA： digit digit nat对应的DFA如下图 digit = [0-9] nat = digit + signedNat = ( +|- )? nat number = signedNat(“·”nat)？ signedNat对应的DFA如下图 加上可选的小数部分，数字常量的正则表达式number = signedNat(“·”nat)？ 对应的DFA如下图： digit + digit digit - + digit digit digit - digit digit ? a b b b 接受与正则式ab+|ab*|b* 相同的语言的DFA如下所示： 例4-14：串中只有一个b被如下所示的DFA接受： b not b not b 例4-15：包含最多一个b的串被如下所示的DFA接受： b not b not b 注意二者之 间的区别 定理：如果一个DFA M 的输入字母表为∑，则我们也称M是∑上的一个DFA。可以证明：∑上的一个字集V ∑*是正规的，当且仅当存在∑上的DFA M，使得V =L(M)。 DFA的确定性表现在映射δ： S×∑→S是一个单值函数。即：对于任何状态s∈S和输入符号a∈∑， δ(s,a)唯一确定了一个状态。 从转换图角度，我们也可以得到答案。 如果允许是一个多值函数，我们就得到下一节要讲到的非确定自动机的概念。 一个非确定有限自动机（NFA） M是一个五元式： M ＝ (S,∑,δ,S0 ,F) ，其中 1、S是一个有限集，它的每个元素称为一个状态 2、∑是一个有穷字母表，它的每个元素称为一个输入字符 3、δ是一个从S×∑*至S的子集的映射，即δ： S×∑* → 2s 4、 S0 S是一个非空初态集 5、 F S是一个终态集（可空）。 一个含有m个状态和n个输入字符的NFA可用一张如下的状态转换图来表示：该图含有m个状态结点，每个结点可以射出若干条弧与别的结点相连接，每条弧用∑*中的一个字（可以是不同的字，也可以是空字）做标记，整张图至少含有一个初态结点和若干个（可以为0）终态结点。某些结点既可以是初态结点也可以是终态结点。 1 aa a,b 2 bb ab 0 a,b 0 1 ab,ba aa,bb ab,ba aa,bb y x 1 5 a a a a b ε b 4 3 2 6 b b ε ε ε 下图所示的状态转换图的S、∑及∑*如下： S = {0,1,2,3} ∑= {a,b} ∑*= {α| α为ε，或者α为a、b的任意组合} 对于∑*中的任何一个字α，若存在一条从某一初态结点到某一终态结点的通路，且这条通路上所有弧上的标记字依序连接成的字（忽略ε）等于α，则称α可以为NFA M 识别。 从初态x到终态y的连接通路弧上，有如下标记字： ε ε a a ε ε，去除ε，为aa，所以字aa可为NFA接受。 1 4 3 2 a a ε b ε ε 例4-16：上图所示的NFA的以下两个转换序列都可以接受串abb： 允许接受ab 允许接受与ab*匹配的字符串 允许接受与b*匹配的字符串 允许接受与ab+匹配的字符串 由此，我们可以看出这个NFA接受与正则式ab+|ab*|b* 相同的语言！ 接受ab 接受ab 接受ab＋ 接受ab 接受ab＋ 接受ab* 接受ab 接受ab＋ 接受ab* 接受b* 练习：考虑以下NFA通过怎样的转换接受串acab： 10 a ε 2 1 b 3 7 5 6 4 8 9 ε ε ε ε ε ε ε ε c DFA是NFA的特