编译原理ch2 词法分析2

本文主要内容为FA分类，DFA、NFA、正则表达式之间的相互转换。

有穷自动机（finite automata）

FA的表示

1. 结点：FA的状态
2. 1 初始状态（开始状态）：只有一个，由start箭头指向
3. 2 终止状态（接收状态）：可以有多个，用双圈表示
4. 带标记的有向边：如果对于输入a，存在一个从状态p到状态q的转换，就在p、 q之间画一条有向边，并标记上a

FA定义（接收）的语言

1. 给定输入串x， 如果存在一个对应于串x的从初始状态到某个终止状态的转换序列，则称串x被该FA接收
2. 由一个有穷自动机M接收的所有串构成的集合称为是该FA定义（或接收）的语言，记为L(M )
   

最长子串匹配原则

FA的分类

本质上是与状态转化图类似的图,有穷（有限）自动机判别输入串的类型；NFA（Nondeterministic Finite Automata）和DFA（Deterministic Finite Automata）。
NFA对其边上的标号没有任何限制，一个符号标记离开同一状态的多条边，并且空串也可以作为标号。DFA对于每个状态和自动机输入字母表中的每个符号，有且只有一条离开该状态，以该符号为标号的边。

确定的有穷自动机DFA

DFA是NFA的一个特例，其中：

1. 没有输入 $\varepsilon$ 上的转换动作
2. 对每个状态 s 和每个输入符号 a ，有且只有一条标号为 a 的边离开 s 。
   接受（a|b）*abb的DFA
   

不确定的有穷自动机NFA

正则式(a|b)*abb表达的语言NFA:

NFA由以下几个部分组成：

1. 有穷的状态集合S。
2. 输入集合符号 $\sum$ ，也即输入字母表，假设代表空串的 $\varepsilon$ 不是 $\sum$ 中的元素。
3. 转换函数（transition function），为每个状态和 $\sum$ $\bigcup$ {$\varepsilon$} 中的每个符号都给出了相应的后继状态（next state）的集合。
4. S 中的一个状态 s_{0} 被指定为开始状态，或者是初始状态。
5. S 中的一个子集 F 被指定为接受状态（或者说终止状态）的集合。

不管是NFA还是DFA，都可以表示为一张转换图（transition graph）。
上图可以使用下面的转换表表示：

等价性

DFA NFA的等价性

带有和不带有“ε-边”的NFA 的等价性

正则表达式和NFA（DFA）的转换

从RE到FA

根据RE构造NFA

举例：RE到NFA转换

NFA和DFA的转换

子集构造法

➢ 输入： NFA N
➢ 输出：接收同样语言的DFA D
➢ 方法： 一开始， ε-closure（s0 ）是Dstates 中的唯一状态，且它未加标记；
while（在Dstates中有一个未标记状态T ）｛
给T加上标记；
for（每个输入符号a）｛
U = ε-closure(move(T, a));
if ( U不在Dstates中)
将U加入到Dstates中，且不加标记；
Dtran[T, a]=U ;
}
}

计算 ε-closure (T )

将T的所有状态压入stack中；
将ε-closure（T ）初始化为 T ；
while（stack非空）｛
将栈顶元素 t 给弹出栈中；
for（每个满足如下条件的u ：从t出发有一个标号为ε的转换到达状态u)
if ( u不在ε-closure（T ）中）｛
将u加入到ε-closure（T ）中；
将u压入栈中;
}
}

赏

谢谢你请我吃糖果

支付宝

微信