词法分析
-
NFA与DFA的等价性：
对于每个NFA M ′都一定存在一个DFA M，使L(M′)=L(M)。
-
NFA转DFA子集法：
状态集合I的ε-闭包：ε-closure(I)，表示I中任意状态S经过任意条ε弧能到达的状态的集合。
-
<u>首先从初态S开始，计算它的ε-closure(S)为I0，然后计算当前状态下对于输入符号∑中任意字符a的
ε-closure(move(I~0~，a))为Ia，</u>如果Ia曾在状态中出现过，则将它标记，否则说明它是新的状态集合，后面会对它进行操作。 -
将没有标记的某个Ia作为I1，将它标记，重复上面的操作。
-
所有状态均标记则转换完成。
例： 将下图中的NFA转换为DFA
NFA
解：
状态 I Ia Ib 0 （初态） {<u>0</u>,1,2,4,7} {<u>3,8</u>,6,7,1,2,4}✔️ {<u>5</u>,6,7,1,2,4}✔️ 1 {<u>3,8</u>,6,7,1,2,4} {<u>3,8</u>,6,7,1,2,4}✔️ {<u>5,9</u>,6,7,1,2,4}✔️ 2 {<u>5</u>,6,7,1,2,4} {<u>3,8</u>,6,7,1,2,4}✔️ {<u>5</u>,6,7,1,2,4}✔️ 3 {<u>5,9</u>,6,7,1,2,4} {<u>3,8</u>,6,7,1,2,4}✔️ {<u>5,10</u>,6,7,1,2,4}✔️ 4（终态） {<u>5,10</u>,6,7,1,2,4} {<u>3,8</u>,6,7,1,2,4}✔️ {<u>5</u>,6,7,1,2,4}✔️ 重新命名后的状态转换矩阵:
状态 I a b 0 （初态） {<u>0</u>,1,2,4,7} 1 2 1 {<u>3,8</u>,6,7,1,2,4} 1 3 2 {<u>5</u>,6,7,1,2,4} 1 2 3 {<u>5,9</u>,6,7,1,2,4} 1 4 4（终态） {<u>5,10</u>,6,7,1,2,4} 1 2 DFA
)
-
-
DFA的最小化：
-
消除多余状态：
从DFA初态进入遍历所有状态，从未被访问过的状态就为多余状态。可以删除状态以及相关的弧。
-
合并等价状态（分割法）：
①首先将DFA的状态集分为两个状态区间：非终态区间和终态状态区间。
②然后对于每个状态区间采用下面的方法检查是否可以分割：
对于某一种输入字符，计算状态区间中每个字符对于该输入的转移状态，每个字符的转移状态按照是否属于当前状态区间分类，即转移状态属于当前状态区间为一类，转移状态不属于当前状态区间为一类。如果存在两种状态分类则将其分成两个新的状态区间。
③重复以上过程直至无新状态区间产生。
例：将下面的DFA最小化：
DFA
①没有多余状态。
②合并等价状态
DFA的状态集k＝{1，2 ，3，4，5，6，7}
按照终态分类后
{{1，2 ，3，4}，{5，6，7}}
读入a之后
{{1，2 }，{3，4}，{5}，{6，7}}
读入a之后
{{1，2 }，{3}，{4}，{5}，{6，7}}
再读入a或b没有新状态生成。
合并之后
DFA
-
-
正规文法转NFA:
①在原有字母表上增加终态F。
②假设线性文法G＝(VN,VT,P,S), 按照下面方法构造状态转移函数f：
- P中形如A→aB的产生式，则有f(A,a)=B;
- P中形如A→a的产生式，则有f(A,a)=F ;
- 对VT中的每个a，都有f(F,a)= Ø
-
将正规表达式转换成等价的有限自动机，要分三步：
三步