正则表达式到有限状态机

有限状态机广泛应用于计算机科学中，如拼写检查，语法检查，语音识别，编译原理等。
有限状态机M=(S, I, O, f, g, s0): 一个有限的状态集合S，一个有限的输入字母表I，一个有限的输出字母表O，转换函数f，输出函数g，初始状态s0。(有限状态机具有输出，而在编译中用到的有限自动机，没有输出)。

来看一个有限状态机的例子:
单位延迟机是电子装置的一个重要部件，它的作用是将输入串延迟一定时间后输出，我们来构造一个延迟一个单位时间的延迟机，例如:x1x2x3...xk如何输出0x1x2x3...xk-1。
s0出发第一个转移输出0，从s1出发每个转移都输出1，从s2出发每个转移都输出0。该单位延迟机的状态如下图所示。

下面介绍有限自动机，有限自动机最重要的应用之一就是语言识别。在设计编译器方面，有限自动机很重要，它可以用来匹配关键字，标识符等字符串的集合。有限自动机分为确定的有限自动机(DFA)和不确定的有限自动机(NFA)。

NFA有以下几个部分：
1) 一个有限的集合S
2) 一个输入字母表I
3)一个转换函数f
4)开始状态s0
5)终止状态F
NFA比有限状态机少了一个输出字母表O，一个输出函数g，多了一个终止状态F，NFA对其边上的标号没有任何限制，它可以是一个集合。一个符号标记离开统一状态的多条边。例如:

上图的NFA转换图表示的是正则表达式(a|b)*abb，该转换图和状态转换图很像，但NFA的转换图的边可以是一个字母集合和epsilon。

DFA与NFA相似不过DFA有且只有一条离开某个状态的边，并且NFA没有epsilon上的转换。

由于NFA可以有多条边到另一个状态即转换表中一个字母有一个转换集合，而DFA只有一条以该符号为标号的边到另一个状态，所以计算机模拟DFA来说更容易，而模拟NFA很困难，因为计算机没有"预测"的能力，所以我们需要将NFA转换为DFA后进行模拟。

模拟DFA的算法:

s = s0;
c = nextchar();

while (c != EOF) {
    s = move(s, c);
    c = nextchar();
}
if (s in F?) return 1;
else return 0;

下一文章描述NFA如何转换为DFA以及如何将正则表达式转换为NFA。

引用:
Discrete Mathematics and Its Applications(Six Edition)    Kenneth H.Rosen
编译原理(第二版)       

Alfred V.Aho, Monica S.Lam, Ravi Sethi, Jeffery D.Ullman