Chinaunix首页 | 论坛 | 博客
  • 博客访问: 598219
  • 博文数量: 5
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 56
  • 用 户 组: 普通用户
  • 注册时间: 2019-06-26 09:19
文章分类
文章存档

2019年(5)

我的朋友

分类: C/C++

2019-07-06 10:03:36

有限状态机广泛应用于计算机科学中,如拼写检查,语法检查,语音识别,编译原理等。
有限状态机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的算法:

点击(此处)折叠或打开

  1. s = s0;
  2. c = nextchar();

  3. while (c != EOF) {
  4.     s = move(s, c);
  5.     c = nextchar();
  6. }
  7. if (s in F?) return 1;
  8. 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

阅读(3630) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~