"早起才能早睡" from <觉主语录>
有一个月没有更新日志了,dave要宣布一个非常不好的消息:系里以没有老师能够指导编译方向为由,拒绝了我的毕业设计选题。dave当时就想说:诺大一个万余人的University,居然还好意思说没有老师能够指导,这也显得学生我太NB了吧,真不好意思在这里继续读下去了。无奈选择了XX管理系统,所以这日志也应该是我今年最后一篇了吧。
这次内容是有穷自动机(finite automata),在说这个有穷自动机前需要两个辅助的工具。转换图(transition graph)和转换表(transition table)。
有穷自动机在本质上是与状态转换图(transition diagram)类似,用来匹配一个输入串。但是它的功能仅限于识别一个输入串是否能够被自动机匹配,返回值要么为真要么为假。有穷自动机分为两类:
1、不确定的有穷自动机(Nondeterministic Finite Automata,以后简称NFA)对其边上标记符号没有任何限制,一个符号可以标记离开同一状态的多个边,空串ε也可以作为标记。
NFA由以下几个部分组成:
1)、一个有穷的状态集合S。
2)、一个输入符号集合Σ,即输入字母表(input alphabet)。
3)、一个转换函数(transition function),它为每个状态和Σ∪{ε}中每个符号都给出了相应的后继状态的集合。
4)、S中的一个状态s0 被指定为开始状态。
5)、S的一个子集F指定为接受状态(或者终止状态)集合。
举例,正则语言(a|b)*abb
转换图-1:
转换表-1:
a |
b |
ε |
|
0 |
0,1 |
0 |
φ |
1 |
φ |
2 |
φ |
2 |
φ |
3 |
φ |
3 |
φ |
φ |
φ |
2、确定由有穷自动机(Deterministic Finite Automata,以后简称DFA)中有且仅有一条该符号标记的离开同一状态的边。
DFA是NFA的特例,跟NFA的区别就是:
1)、没有输入ε的转换动作
2)、对于每个状态s和每个输入符号a,有且仅有一条标号为a的边离开s。
举例,还是上面的正则语言(a|b)*abb
转换图-2:
转换表-2:
a |
b |
|
0 |
1 |
0 |
1 |
1 |
2 |
2 |
1 |
3 |
3 |
1 |
0 |
NFA和DFA能识别的语言集合与正则表达式描述的语言集合都是相同的,统称这种语言为正则语言(regular language)。NFA抽象的表示了用来识别某个语言中串的算法,而对应的DFA则是一个简单具体的识别算法。在构造词法分析器的时候,我们真正实现或者模拟的是DFA。每个正则表达式和NFA都是可以转化为DFA的。接下来就是重点NFA--〉DFA的子集构造法。
子集构造法的主要思想是:让DFA的一个状态对应NFA中一个状态集合,这样来解决NFA中接受某符号后状态不确定的问题。
输入:NFA N
输出:DFA D
操作:move(T,a):返回N中从状态集合T任一状态出发通过符号a转换到达的状态集合。
addInSet(T):把T加入一个集合
isInSet(T):判断T是否属于集合
push(T):将状态集合T入栈
pop():状态集合T出栈
isEmpty();栈是否空
伪码:
- s0=N的初始状态集合;
- NIA=N的输入符号集,排除ε;
- D[][]=D的状态转换表;
- T=move(s0,ε);
- addInSet(T);
- push(T);
- while(!isEmpty())
- {
- T=pop();
- for each token in NIA
- {
- U=move(move(T,token),ε);
- if(!isInSet(U))
- {
- push(U);
- addInSet(U);
- }
- D[T][token]=U;
- }
- }
数据演示:就用上面(a|b)*abb的例子
第一次while循环后的D:
a |
b |
|
0 |
0,1 |
0 |
第二次:
a |
b |
|
0 |
0,1 |
0 |
0,1 |
0,1 |
0,2 |
第三次:
a |
b |
|
0 |
0,1 |
0 |
0,1 |
0,1 |
0,2 |
0,2 |
0,1 |
0,3 |
第四次:
a |
b |
|
0 |
0,1 |
0 |
0,1 |
0,1 |
0,2 |
0,2 |
0,1 |
0,3 |
0,3 |
0,1 |
0 |
用A代表0 B代表0,1 C代表0,2 D代表0,3,由于D中包含接受状态3,所以D也是接受状态
a |
b |
|
A |
B |
A |
B |
B |
C |
C |
B |
D |
D |
B |
A |
这个表格跟转换表2是一致的,检验了该算法的正确性。
PS:即使一度分离,也终会再次相逢。
davelv
于09年12月05日