Question

有穷自动机如何实现？

1.1.1.注释的识别
内容：一个接受具有“C注释风格”的语言的有穷状态自动机

用熟悉的编程语言编写程序实现注释的识别。

注释的文法：可以不给出。

识别注释的有穷自动机：

该程序的输入

该程序的输出

/*sd**/

这是一个注释

/*sd*

这不是一个注释

/*sd**/djk

这不是一个注释

jk/*sd**/

这不是一个注释

/sd*

这不是一个注释

1.1.2.标识符的识别

内容：一个接受“标识符”语言的有穷状态自动机

用熟悉的编程语言编写程序实现标识符的识别。

标识符的文法：

标识符的文法：

其中，字母包括
，数字包括
。

识别标识符的有穷自动机：

该程序的输入

该程序的输出

Abs12

这是一个标识符

a@sc

这不是一个标识符

2asc

这不是一个标识符

1.1.3.实常数的识别

实验内容：一个接受“实常数”语言的有穷状态自动机

用熟悉的编程语言编写程序实现实常数的识别。

实常数的文法：自己给出。

识别实常数的有穷自动机的状态转换图：

该程序的输入

该程序的输出

1.2e-10

这是一个实数

123.456

这是一个实数

2asc

这不是一个实数





Answer 1

有穷自动机，或有穷状态的机器，是描述（或“机器”）特定类型算法的数学方法。特别地，有穷自动机可用作描述在输入串中识别模式的过程，因此也能用作构造扫描程序。当然有穷自动机与正则表达式之间有着很密切的关系，在下一节中大家将会看到如何从正则表达式中构造有穷自动机。但在学习有穷自动机之前，先看一个说明的示例。通过下面的正则表达式可在程序设计语言中给出标识符模式的一般定义（假设已定义了letter 和digit）：identifier = letter ( letter | digit ) *它代表以一个字母开头且其后为任意字母和/ 或数字序列的串。
有穷自动机　　通过标明数字1 和2 的圆圈表示的是状态（state），它们表示其中记录已被发现的模式的数量在识别过程中的位置。带有箭头的线代表由记录一个状态向另一个状态的转换（transition），该转换依赖于所标字符的匹配。有穷自动机又分为确定型的有穷自动机（DFA）与非确定型的有穷自动机（NFA）两种。http://www.douban.com/note/74804011/