ch3.词法分析（1）——有穷自动机（续）

NFA存在的问题

  1、开始状态不确定：开始状态可能有数个，无法确定该从哪一个状态开始
  2、状态转换不确定：接收一个输入，可能会使得状态转移到多个状态中的一个
  3、 ϵ \epsilon ϵ（空弧）带来的不确定性：有些状态之间的转换关系是 ϵ \epsilon ϵ，即没有输入也能进行状态转换。在此情形下，状态也是不确定的

NFA到DFA的转换

  基本思想：从原本的状态间的转换关系，通过构造集合的方法，转变为状态子集之间的转换关系。
  形象地讲，假设A要去P、Q、R三个地点中的一个，那么就可以类比状态转换图中的，同一个输入对应3种可能到达的状态，这显然是NFA的。但如果将P、Q、R合并为S={P、Q、R}，那么就可以认为A只到达S地点

  转换的方法包括子集法和造表法

  为了解决NFA存在的问题1和问题3，引入 ϵ \epsilon ϵ闭包的定义：

ϵ \epsilon ϵ闭包

  符号表示：状态子集 I I I的 ϵ \epsilon ϵ闭包记做 ϵ − C L O S U R E ( I ) \epsilon-\mathrm{CLOSURE}(I) ϵ−CLOSURE(I)（为了方便记录，之后记做 ϵ − I \epsilon-I ϵ−I）

   ϵ − I \epsilon-I ϵ−I的计算方式：对于每个状态 a ∈ I a\in I a∈I，都从 a a a出发，不断地通过 ϵ \epsilon ϵ边去搜索能够到达的其他状态，并将所有搜索到的其他状态加入到 I I I中
例如：在图1中，{1}的闭包为{1, 2}，因为从状态1出发，经过空弧可以到达状态2

图1

  解决NFA的开始状态不唯一这一问题的方法：求 Q 0 Q_0 Q0​的 ϵ \epsilon ϵ闭包，使其包括因空弧而可能成为开始状态的状态，从而使得开始状态是唯一的

  至此，问题1和问题3得到解决，对于剩下的问题2，引入 I a I_a Ia​子集：

I a I_a Ia​子集

  定义：若将从状态集 I I I中的任一状态出发，经过一条a弧（跳过 ϵ \epsilon ϵ弧），能够到达的状态的集合称为 J J J，则 I a = ϵ − C L O S U R E ( J ) I_a=\epsilon-\mathrm{CLOSURE}(J) Ia​=ϵ−CLOSURE(J)

  例如，在图1中， I 1 = { 5 ,   4 ,   6 ,   2 ,   7 } I_1=\{5,\ 4,\ 6,\ 2,\ 7\} I1​={5, 4, 6, 2, 7}

  将子集的{}改为[]，用于表示整体——整体间的转换关系

  子集法可行的原因：重点在于能否识别符号串，而不在乎是在哪个状态下识别

转换举例

  现有如图2所示的NFA状态转换图，目标是将其转换为DFA

图2

  首先开始状态为S，求其 ϵ \epsilon ϵ闭包 ϵ − S \epsilon-S ϵ−S得到{S, A, C, B}，将其记为 q 0 q_0 q0​，随后对 q 0 q_0 q0​求 I a I_a Ia​，得{A, B, C, D}，记为 q 1 q_1 q1​。求 I b I_b Ib​得{A, B, C, Z}，记为 q 2 q_2 q2​

  因为还未对{A, B, C, D}和{A, B, C, A}求 I a I_a Ia​和 I b I_b Ib​，所以分别对它们进行同样的操作，直到最后没有新的状态集产生。这样得到的状态集之间满足DFA：对于某一状态时的单一输入，到达的状态唯一

DFA最小化

  关键在于寻找等价状态

  状态p和q是等价状态的定义为：从DFA出发的某个状态p导出的符号串集合，与由状态q导出的符号串集合相等

  通过不断地对集合进行划分，以此寻找等价关系

  首先根据开始状态和终止状态，将集合划分为两个。随后分别分析两个集合中的各个元素，在获取不同输入时，到达的状态是否是在同一个集合中，如果不是，则将其继续划分拆开。直到最后无法再进行划分拆开时，即得到了各等价集合，随后即可对其进行合并

  例如，对于图3而言，集合划分的结果为{F}，{G}，{H}，{I, J}，因此，I和J可以合并，合并结果如图4所示：

图3

图4

正规文法与有穷自动机

  正规语言：在构成上，具有规律的语言
  有穷自动机，正规语言和正规表达式可以互相转换

  对于右线性的文法G[S]，可以从语法树的根结点出发，对其构造DFA：A，步骤为：
  1、令G的终结符号集为A的字母表
  2、G的非终结符号作为A的状态，G的开始符号为A的开始状态
  3、增加一个终止状态Z（Z不是非终结符）
  4、形如U → \rightarrow →aW的规则，引一条从状态U到W的a弧
  5、形如U → \rightarrow →a的规则，引一条从状态U到终止状态Z的标记为a的弧

  对于左线性的文法G[S]，方法与右线性时相似，只不过是从根结点出发，并且新增一个开始状态：
  1、令G的终结符号集为A的字母表
  2、G的非终结符号作为A的状态，G的开始符号为A的终止状态
  3、增加一个开始状态S（S不是非终结符）
  4、形如U → \rightarrow →Wa的规则，引一条从状态W到U的a弧
  5、形如U → \rightarrow →a的规则，引一条从开始状态S到状态U的标记为a的弧

  从FA到正规文法：与正规文法到FA类似，只不过是其逆过程。注意对于 U → ϵ U\rightarrow \epsilon U→ϵ的产生式，可以进行简化：将其删除，并对其他产生式中含有U的部分进行相应的修改