Compile Principle Chapter 3 Notes

Key: DFA、NDFA, NDFA到DFA的转换, 正规文法与FA, 正规表达式与FA

编译原理 3rd 章笔记

有穷自动机的形式定义

确定的有穷自动机DFA （5元组）

DFA=(Q，$\sum$，t，$q_0$ ，F)

Q—有穷非空的状态集。

$\Sigma$— 有穷的输入字母表 。

$q_0$ 一 $\in{Q}$, 是开始状态 。

F——$\subseteq\mathbb{Q}$, 非空终止状态集合 。

t — 单值映射$\mathbb{Q}\times\Sigma{\to}\mathbb{Q}$​。t(q,x)=q'

“确定”: 当前状态和下一个输入字符惟一地确定了后继状态。

表示

FA的表示：

1. 状态转换表

   列key为字母(路径),行Key为状态

   

2. 状态转换图

   类似数电里学的状态转移图，只不过终态用双圆圈

   

如此，有穷自动机就可以识别符号串了

FA等价性

如果两个有穷自动机A_1和A_2满足

则称自动机$A_1$和$A_2$是等价的。

非确定的有穷自动机NDFA （5元组）

非确定的有穷自动机NDFA

$\mathbf{NDFA=}(\mathbf{Q},\:\sum,\:\mathbf{t},\:\mathbf{Q}_0,\:\mathbf{F})$

Q一有穷非空的状态集。

$\sum\textbf{— 有穷的输入字母表}$

$\mathbb{Q}_0\xrightarrow{}{\subseteq}\mathbb{Q}$, 是开始状态集 。

F— $\subseteq\mathbb{Q}$, 非空终止状态集合 。

t— 多值映射 $\mathbb{Q}\times\Sigma\to2^\mathbb{Q}$ 。

NDFA与DFA的转换

• DFA是NDFA的特例
• 对每个NDFA N一定存在一个DFA M，使得L(M)=L(N)。即对任意的NDFA N存在与之等价的DFA M。但这种DFA M可能不唯一

确定化-造表法

一些定义

---

为避免不可达状态，从初始状态出发，计算t′，依次构造其后继状态，进行确定化

完整过程参考示例请见NFA的确定化珞辰的技术博客51CTO博客

---

最小化，化简

完整过程参考示例请见DFA 的化简_dfa化简-CSDN博客

寻找一个状态数比M更少的DFA Mˊ，使得M和Mˊ所识别的字符串相同，即L(M)=L(Mˊ)。（Mˊ唯一的）

条件：接受的语言相同（等价的DFA）

主要思想：

• 合并等价状态

  • 等价状态 ：如果从DFA 的某个状态q1出发能识别某一字符串x而停止于终态，那么从q2出发也能识别字符串x而停止于终态；反之亦然。则称状态q1 和q2 是等价的。如果q1 和q2 不等价，则说q1 和q2 是可区分的。

    Note
    

    两个终态不一定相等，假设有两个终止态F1，F2，但是这两个终止态又是等价的

  • 最小化算法（划分法）：DFA最小化的关键在于把它的状态集分成一些两两互不相交的子集，使得任何两个不同的子集中的状态都是可区分的，而同一子集中的任何两个状态都是等价的

• 删除无关状态

步骤一 构造状态集的划分

• 终止状态集 / 非终止状态集
• 对每一个子集进行再分解（属于同一子集的任意状态q1和q2，对于任何a $\in \sum$ ，t(q1 ,a)与t(q2 ,a)属于同一子集。）

步骤二 取每一组中的一个状态作代表 ，合并等价状态

步骤三 删去无关状态

• 不可达状态
• 死状态

 

正规文法与FA

RG: 生成规则，FA：识别（接受）

定理

1. RG$\to$FA 由正规文法G[S]可直接构造一个与之等价的FA A，使得L(G)=L(A)。
2. FA$\to$RG 由有穷自动机FA A可直接构造一个与之等价的正规文法G，使得L(G)=L(A)。

构造

1. RG$\to$FA的构造：

• 令G的终结符号集为A的字母表；
• 增加一个终止状态Z（Z$\notin V_N$）；
• 形如U→a的规则，引一条从状态U到终止状态Z的标记为a的 弧；
• 形如U→aW的规则，引一条从状态U到W的a弧。

2. FA $\to$ RG的构造

   1. 自动机A中的每一个状态均作为G的非终结符号，其中A的开始状态作为G的开始符号，A的输入字母表中的所有符号作为G的终结符号；

   2. 对A中$\mathrm{V\in t( U, a) }$的映射，构造G的产生式U$:: =$aV$;$ 若$\mathrm{V\in F}$, 则构造G的产生式 U::=a;

      3. 若A中$q_0{\in}\mathbb{F}$, 则构造G的产生式S$::=\varepsilon$​。

3. FA $\to$ RG的构造

   1. 自动机A中的每一个状态均作为G的非终结符号，其中A的开始状态作为G的开始符号，A的输入字母表中的所有符号作为G的终结符号:
   2. 对A中$\mathrm{V\in t( U, a) }$的映射，构造G的产生式U::=aV;
   3. 对A中终止状态Z，构造G的形如Z::=$\varepsilon$​的产生式。

 

正规(正则)表达式RE

不在赘述，重点是使用汉语简介地描述正则表达式的含义

注意用词

举例

$(1)\quad0*10*$

$(2)\quad\sum^*1\sum^*$

$(3)\quad\sum*001\sum*$

$(4)\quad(\Sigma\Sigma)^*$

$(5)\quad(\Sigma\Sigma\Sigma)*$

$(6)\quad0\sum*0\mid1\sum*1\mid0\mid1$

$(7)\quad(0\mid\varepsilon)1^*=01^*\mid1^*$

(8) Ф$^{*}=\{\varepsilon\}$​​

定义

正规表达式等价

设e1，e2均为∑上的正规表达式，若 L(e1 )=L(e2 )，则称e1与e2等价，记为：e1 =e2。

如b(ab)* = (ba)*b

end ppt 62nd page

Read More