国防科技大学编译原理第6讲词法分析3

课程主页：

https://www.icourse163.org/course/NUDT-1003101005?tid=1460976445

这次回顾第6讲：词法分析3。

第6讲词法分析3

有限自动机的等价性

有限自动机的等价性——NFA转换成DFA

DFA与NFA的等价性

对于每个NFA M存在一个DFA $M’$，使得$L(M)=L(M’)$
- 等价性证明
- NFA的确定化
思路： NFA 和DFA的差别

	NFA	DFA
初始状态	不唯一	唯一
弧上的标记	字(单字符字、$ε$)	字符
转换关系	非确定	确定

DFA与NFA的等价性证明

假定NFA $M=\langle S, \Sigma, \delta, S_0, F \rangle$，我们对$M$的状态转换图进行以下改造：
- 引进新的初态结点$X$和终态结点$Y$，$X,Y∉S$，从$X$到$S_0$中任意状态结点连一条$ε$箭弧，从$F$中任意状态结点连一条$ε$箭弧到$Y$。(解决初始状态唯一性)
- 对$M$的状态转换图进一步施行替换，其中$k$是新引入的状态。(简化弧上的标记)
  
  例子：
- NFA确定化——子集法(解决$ε$弧和转换关系)
  - 设$I$是的状态集的一个子集，定义$I$的$ε$-闭包$ε-\text{closure}(I)$为:
    - 若$s∈I$，则$s∈ε-\text{closure}(I)$；
    - 若$s∈I$，则从$s$出发经过任意条$ε$弧而能到达的任何状态$s’$都属于$ε-\text{closure}(I)$
    - 即
      $ε-\text{closure}(I)=I∪\{s’|从某个s∈I出发经过任意条ε 弧能到达s’\}$
  - 设$a$是$Σ$中的一个字符，定义
    $I_a= ε-\text{closure}(J)$
    其中，$J$为$I$中的某个状态出发经过一条$a$弧而到达的状态集合。
  - 例子：
    
    $\begin{aligned} \varepsilon-\operatorname{closure}(\{1\}) &=\{1,2\}\\ &=I\\ J&=\{5,4,3\}\\ \mathrm{I}_{\mathrm{a} } &=\varepsilon-\mathrm{closure}(\mathrm{J})\\ &=\varepsilon-\operatorname{closure}(\{5,4,3\})\\ &=\{5,4,3,6,2,7,8\} \end{aligned}$

确定化的具体过程

确定化：不失一般性，设字母表只包含$a$和$b$，我们构造一张计算状态集的转换表:
- 首先，置第1行第1列为$ε-\text{closure}(\{X\})$（唯一初态的闭包），求出这一列的$I_a，I_b$；
- 然后，检查这两个$I_a，I_b$，看它们是否已在表中的第一列中出现，把未曾出现的填入后面空行的第1列上，接着求出每行第2，3列上的集合…
- 重复上述过程，直到所有第2，3列子集全部出现在第一列为止
例子：
把表看成状态转换矩阵，子集视为状态
- 转换表唯一刻划了一个确定的有限自动机$M$
  - 初态是$ε-\text{closure}(\{X\})$
  - 终态是含有原终态$Y$的子集
- 不难看出，这个DFA $M$与$M’$等价
- 对于每个NFA $M$存在一个DFA $M ’$ ，使得$L(M)=L(M’)$
- NFA和DFA等价
例子：

有限自动机等价性——DFA的化简

确定有限自动机的化简

DFA的化简(最小化)
- 对于给定的DFA $M$，寻找一个状态数比$M$少的DFA $M’$，使得$L(M)=L(M’)$
状态的等价性
- 假设$s$和$t$为$M$的两个状态，称$s$和$t$等价：如果从状态$s$出发能读出某个字$α$而停止于终态，那么同样，从$t$
  出发也能读出$α$而停止于终态；反之亦然
- 如果两个状态不等价，则称它们是可区别的
基本思想
- 把$M$的状态集划分为一些不相交的子集，使得任何两个不同子集的状态是可区别的，而同一子集的任何两个状态是等价的。
- 最后，让每个子集选出一个代表，同时消去其他状态。

初始划分

按照上述原则对DFA的状态集合S进行第一次划分，正确的分法是( )
- A. 初态和非初态
- B. 终态和非终态
- C. 初态、终态、其他状态

选择B。

化简的过程

首先，把$S$划分为终态和非终态两个子集，形成基本划分$\Pi$。
假定到某个时候，$\Pi$已含$m$个子集，记为$\Pi=\{I^{(1)} ,I ^{(2)},…,I^{(m)}\}$，检查$\Pi$中的每个子集，查看看是否能进一步划分：
- 对某个$I^{(i)}$，令$I^{(i)}=\{s_1,s_2, \ldots,s_k\} $ ，若存在一个输入字符$a$使得$I_{a}^{(i)}$不会包含在现行$\Pi$的某个子集$I^{( j)}$中，则至少应把$I^{(i)}$分为两个部分。
- 假定状态$s_1$和$s_2$是$I^{(i)}=\{s_1,s_2, \ldots,s_k\} $中的两个状态，它们经$a$弧分别到达$t_1$和$t_2$，而$t_1$和$t_2$属于现行$\Pi$中的两个不同子集
  - 说明有一个字$α$，$t_1$读入$α$后到达终态，而$t_2$读入$α$后不能到达终态，或者反之
  - 那么对于字$aα$ ， $s_1$读出$aα$后到达终态，而$s_2$读出$aα$不能到达终态，或者反之
  - 所以$s_1$和$s_2$不等价
- 将$I^{(i)}$分成两半，一半含有$s_1$，一半含有$s_2$
  - $I^{(i_1)}$含有$s_1: I^{(i_1)} =\{s|s∈I^{(i)}且s经a弧到达t, 且t与t_1属于现行Π中的同一子集\}$
  - $I^{(i_2)}$含有$s_2 : I^{(i_2)}=I^{(i)}-I^{(i_1)}$
一般地，对某个$a$和$I^{(i)}$，若$I_{a}^{(i)}$落入现行$Π$中$N$个不同子集，则应把$I^{(i)}$划分成$N$个不相交的组，使得每个组$J$的$J_a$都落入的$Π$同一子集。
重复上述过程，直到$Π$所含子集数不再增长。
对于上述最后划分$Π$中的每个子集，我们选取每个子集$I$中的一个状态代表其他状态，则可得到化简后的DFA $M’$。
若$I$含有原来的初态，则其代表为新的初态，若$I$含有原来的终态，则其代表为新的终态。

具体例子：

化简过程：

${I}^{(1)}=\{
0,1,2\} , {I}^{(2)}=\{3,4,5,6\}
$
- ${I}_{ {a} }^{(1)}=\{ {1}, {3}\}$
- $1,3$属于不同的集合，所以要对$I^{(1)}$划分
${I}^{(11)}=\{
0,2\} ,{I}^{(12)}=\{1\} ,{I}^{(2)}=\{3,4,5,6\}
$
- ${I}_{ {a} }^{(11)}=\{ {1}\} ,{I}_{ {b} }^{({1 1})}=\{ {2}, {4}\}$
- $2,4$属于不同的集合，所以要对$I^{(11)}$划分
${I}^{(111)}=\{
0\}，{I}^{(112)}=\{
2\} ,{I}^{(12)}=\{1\} ,{I}^{(2)}=\{3,4,5,6\}
$
- $I_a^{(2)} =\{3, 6\}, I_b^{(2)} =\{4, 5\}$
- $3,6$在同一集合，$4,5$在同一集合，划分结束。

化简后：

正规式与有限自动机的等价性

一个正规式$r$与一个有限自动机$M$等价
- $L(r)=L(M)$
FA ->正规式
- 对任何FA $M$，都存在一个正规式$r$，使得$L(r)=L(M)$。
正规式 -> FA
- 对任何正规式$r$，都存在一个FA $M$，使得$L(M)=L(r)$。

正规式与有限自动机的等价性——为NFA构造正规式

为NFA构造正规式

对转换图概念拓广，令每条弧可用一个正规式作标记。
证明：对$Σ$上任一NFA $M$，都存在一个$Σ$上的正规式$r$，使得$L(r)=L(M)$。
假定NFA $M=\langle S, \Sigma, \delta, S_0, F \rangle$，我们对$M$的状态转换图进行以下改造：
- 在$M$的转换图上加进两个状态$X$和$Y$，从$X$用$ε$弧连接到$M$的所有初态结点，从$M$的所有终态结点用$ε$弧连接到$Y$，从而形成一个新的NFA，记为$M’$，它只有一个初态$X$和一个终态$Y$，显然$L(M)=L(M’)$
- 然后，反复使用下面的三条规则，逐步消去结点，直到只剩下$X$和$Y$为止。
  - 例子：注意要对每条路径都替换为等价的路径
- 最后，$X$到$Y$的弧上标记的正规式即为所构造的正规式$r$
- 显然$L(r)=L(M’)=L(M)$
- 得证。

正规式与有限自动机的等价性——为正规式构造NFA

为正规式构造NFA

定理：对任何正规式$r$，都存在一个FA $M$，使得$L(M)=L(r)$。
定理：对于$Σ$上的正规式$r$，都存在一个NFA $M$，使$L(M)=L(r)$，并且$M$只有一个初态和一个终态，而且没有从终态出发的箭弧。
对给定正规式$r$中的运算符数目进行归纳
- 验证$r$中的运算符数目为$0$时，结论成立。
- 假设结论对于运算符数目少于$k(k≥1)$的正规式成立
- 基于该假设，证明结论对于运算符数目为$k$的正规式成立。
若$r$具有零个运算符，则$r=ε$或$r=\varnothing$或$r=a$，其中$a∈Σ$。
- 针对上述$3$类正规式$r$，分别按照下图构造NFA $M$，$M$只有一个初态和一个终态，而且没有从终态出发的箭弧，而且使$L(M)$和对应的$L(r)$相等。
假设对于运算符数目少于$k(k≥1)$的正规式成立。
当$r$中含有$k$个运算符时，$r$有三种情形：
- 情形1：$r=r_1|r_2$，$r_1$和$r_2$中运算符数目少于$k$。从而，由归纳假设，对$r_i$存在$M_i=\langle S_i,\Sigma_i, \delta_i, q_i, \{f_i\}\rangle$，
  使得$L(M_i)=L(r_i)$，并且$M_i$没有从终态出发的箭弧$(i=1,2)$。不妨设$S_1\cap S_2=\varnothing$，在$S_1 \cup S_2$中加入两个新状态$q_0,f_0$。
  - 令$M=\langle S_1\cup S_2\cup \{q_0,f_0\},Σ_1\cup Σ_2, δ, q_0, \{f_0\}\rangle$，其中$δ$定义如下($M$的状态转换如图所示)：
    - $δ(q_0, ε)=\{q_1,q_2\}$
    - $δ(q,a)= δ_1(q,a)$, 当$q∈S_1-\{f_1\},a∈Σ_1\cup\{ε\}$
    - $δ(q,a)= δ_2(q,a)$, 当$q∈S_2-\{f_2\},a∈Σ_2\cup\{ε\}$
    - $δ(f_1,ε)=δ(f_2,ε)=\{f_0\}$
  - $L(M)=L(M_1)∪L(M_2)=L(r_1)∪L(r_2)=L(r_1|r_2)= L(r)$
  - 情形1得证
- 情形2：$r=r_1.r_2$, 设$M_i$同情形1$(i=1,2)$
  - 令$M=\langle S_1∪S_2,\Sigma_1\cup \Sigma_2, \delta, q_1, \{f_2\}\rangle$，其中$δ$定义如下($M$的状态转换如图所示)：
    - $δ(q,a)= δ_1(q,a)$, 当$q∈S_1-\{f_1\},a∈Σ_1∪\{ε\}$
    - $δ(q,a)= δ_2(q,a)$, 当$q∈S_2,a∈Σ_2∪\{ε\}$
    - $δ(f_1,ε)=\{f_0\}$
  - $L(M)=L(M_1)L(M_2)=L(r_1)L(r_2)=L(r_1.r_2)= L(r)$
- 情形3：$r=r_1^{\star}$。设$M_1$同情形1
  - 令$M=\langle S_1\cup \{q_0,f_0\},\Sigma_1, \delta, q_0, \{f_0\}\rangle$，其中$q_0,f_0\notin S_1$，$δ$定义如下($M$的状态转换如图所示)：
    - $δ(q_0, ε)=δ(f_1, ε)=\{q_1,f_0\}$
    - $δ(q,a)= δ_1(q,a)$, 当$q∈S_1-\{f_1\},a∈Σ_1\cup \{ε\}$
  - $L(M) = L(M_1)^{\star} = L(r_1)^{\star} = L(r_1^{\star})= L(r)$