《第二章词法分析.ppt

DFA M对字符串的识别：对于Σ中的任何字符串α，若存在一条从初态结点到终态结点的通路，且这条通路上所有弧的标记符号连接成的串等于α。 若M的初态结点又是终态结点，则空字ε可为M所识别。 DFA M所能识别语言：能被DFA M所接受的字符串的集合，记为L(M). 对于任何两个有穷自动机M和M′，如果 L(M)=L(M′)，则称M与M′是等价的.? Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 结论： ?上一个符号串集V???是正规的，当且仅当存在一个?上的确定有穷自动机M，使得V=L(M)。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. ＤＦＡ的构造 例：构造一个DFA ，他接受字母表{a,b,c}上以a或b开始的字符串，或以c开始所含一个a的字符串。 所以，DFA M=({0,1,2,3},{a,b,c},f,0,{1,2,3}) (a|b(a*|b*|c*))|(c(b*|c*)a(b*|c*)) 0 1 2 3 a b c a b c b c a b c Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2.2.2 不确定的有限自动机（NFA） 一个不确定有限自动机（NFA)是一个五元式： M= (S, Σ,δ,S0, F) 其中: 1. S —有限状态集（非终极符集合）； 2. Σ —输入字母表（终极符集合）； 3. δ —转换函数S ? (??{?}) ? P(S)， 即S ? ?* 到S的幂集(2S)的一种映射； 4. S0 —唯一的初始状态集合 （非空）S0∈S 5. F—终止状态集合 F?S Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 一个NＦＡ的例子 例：设NFA M=（{0， 1 ，2 ，3，4}，{a，b}，δ，{0 }，{2，4}）其中δ定义为 δ（0，a）={0，3} δ （0，b）={0，1} δ （1，b）={2} δ （2，a）={2} δ （2，b ）={2} δ （3，a ）={4} δ （4，a ）={4} δ （4，b ）={4} 0 4 ? a 3 1 2 b b a a ,b a ,b a ,b Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 非确定性是指读入相同的输入字符后继状态可以有多个 DFA是NFA的特例，对于每个NFA M存在一个DFA M”，使L(M)=L(M”)。 （1）没有状态具有ε状态转移(ε-transition)，即状态转换图中没有标记ε的边； （2）对每一个状态s和每一个字符a，最多有一个下一状态。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 正规式 正规集 有限自动机 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2.2.3 NFA到DFA的变换 非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的 主要思想：DFA的每一个状态对应NFA的一组状态. DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态. 变换方法：子集法