词法分析

• NFA与DFA的等价性：

  对于每个NFA M ′都一定存在一个DFA M，使L(M′)=L(M)。

• NFA转DFA子集法：

  状态集合I的ε-闭包：ε-closure(I)，表示I中任意状态S经过任意条ε弧能到达的状态的集合。

  1. <u>首先从初态S开始，计算它的ε-closure(S)为I₀，然后计算当前状态下对于输入符号∑中任意字符a的ε-closure(move(I~0~，a))为I_a，</u>如果I_a曾在状态中出现过，则将它标记，否则说明它是新的状态集合，后面会对它进行操作。

  2. 将没有标记的某个I_a作为I₁，将它标记，重复上面的操作。

  3. 所有状态均标记则转换完成。

  例： 将下图中的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的最小化：

  1. 消除多余状态：

     从DFA初态进入遍历所有状态，从未被访问过的状态就为多余状态。可以删除状态以及相关的弧。

  2. 合并等价状态（分割法）：

     ①首先将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：

  1. P中形如A→aB的产生式，则有f(A,a)=B;
  2. P中形如A→a的产生式，则有f(A,a)=F ;
  3. 对V_T中的每个a，都有f(F,a)= Ø

• 将正规表达式转换成等价的有限自动机，要分三步：