编译器笔记6-词法分析-有穷自动机

有穷自动机(Finite Automata，FA)由两位神经物理学MeCuloch和Pitts于1948年首先提出，是对 一类处理系统建立的数学模型。这类系统具有一系列离散的输入输出信息和有穷数目的内部状态（状态：概括了对过去输入信息处理的状况）。

成都创新互联网络公司拥有10余年的成都网站开发建设经验，上千多家客户的共同信赖。提供做网站、成都做网站、网站开发、网站定制、卖友情链接、建网站、网站搭建、响应式网站设计、网页设计师打造企业风格，提供周到的售前咨询和贴心的售后服务

系统只需要根据当前所处的状态 和 当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部 状态也将发生改变。

电梯控制装置

输入：顾客的乘梯需求（所要到达的层号）

状态：电梯所处的层数+

电梯控制装置并不需要记住先前全部的服务要

求，只需要知道电梯当前所处的状态以及还没

有满足的所有服务请求。

输入带 (input tape) ：用来存放输入符号串。

读头 (head) ：从左向右逐个读取输入符号，不能修改（只读）、不能往返移动。

有穷控制器 ( finite control ) ：具有有穷个状态数，根据当前的

状态和当前输入符号控制转入 下一状态。

确定的FA (Deterministic finite automata, DFA)

非确定的FA (Nondeterministic finite automata, NFA)

M = (S，Σ，δ，s0，F)

例：一个DFA

M = (S，Σ ，δ，s0，F)

M = (S，Σ，δ，s0，F)

例：一个NFA

M = (S，Σ，δ，s0，F)

对任何非确定的有穷自动机N，存在定义同一语言的确定的有穷自动机D。对任何确定的有穷自动机D，存在定义同一语言的非确定的有穷自动机N。

DFA和NFA可以识别相同的语言

M = (S，Σ，δ，s0，F)

从正则表达式到NFA相对直接到DFA比较简单,再从NFA转到DFA。

例 r=(a|b)* abb 对应的NFA

与NFA等价的DFA的每个状态都是NFA状态的一个子集

move(T,a)获得的是一个状态集合U，ε-closure（move(T,a)）即为ε-closure(U)对应上表的第二个操作。所以理解上述函数关键是理解closure(T),该操作其实就是求得一个状态集合只通过ε转换得到的另外一个集合。

有穷自动机

计算理论要面对的第一个问题是：什么是计算机？现实的计算机相当复杂，很难直接为它们建立一个容易处理的数学理论，因此采用称为 计算模型 的理想计算机来描述，本篇就从最简单的 有穷自动机 讲起。

通常在对现实问题建立数学模型的初期，最重要的是对问题进行抽象的描述，如下图，采用状态图来描述一个有穷自动机 ：

如图所示被称为 的状态图，它包含3个状态，记作 、 和 。 起始状态 用一个指向它的无出发点的箭头表示， 接收状态 带有双圈。从一个状态指向另一个状态的箭头称为 转移 ；这里需要注意的是处理从 M 1 的起始状态开始，自动机从左至右一个一个字符读取字符串中的所有字符，根据不同的状态转移路径到不同的状态，直到读取到最后一个字符时 产生它的输出。如果 现在处于接受状态，则输出为接收，否则输出为拒绝。

例如，输入的字符串为 1101 ，用上述的有穷自动机 处理步骤如下：

形式化定义把一台有穷自动机描述成一张含有以下5部分的表：状态集、输入字母表、动作规则、起始状态以及接受状态集。用数学语言表达，5个元素的表经常称为5元组；

这里略作解释一下 动作规则 ，在描述中用 转移函数 定义动作规则，常记作 。如果有穷自动机从状态 到状态 标有输入符号 1 的箭头，这就表示它处于状态 时读取到 1，则转移到状态 ，则用转移函数记作 ；

因此可以描述 有穷自动机 是一个5元组 ，其中

此时可以给出 的形式化定义: ，其中

这里需要说明的是若 是机器 接受的全部字符串集，则称 是 机器 的语言 ，记作 。又称 识别 或 接受 。一台机器可能接受若干字符串，但是永远只能识别一个语言。如果机器不接受任何字符串，那么它仍然识别一个语言，即空语言 。

设 是一台有穷自动机， 是一个字符串并且其中任一 是字母表 的成员，如果存在 中的状态序列是 ，满足下述条件：

则称 接受

怎么理解呢？ 状态都是由上一个状态 以及输入的字符 决定的，比如 时， 即为初始状态，那么当输入为 时，输出为 ，以此类推...，当得到 时，则认为 接受 。

如果 接受 ，则称 识别语言 。

有穷自动机如何实现？

有穷自动机，或有穷状态的机器，是描述（或“机器”）特定类型算法的数学方法。特别地，有穷自动机可用作描述在输入串中识别模式的过程，因此也能用作构造扫描程序。当然有穷自动机与正则表达式之间有着很密切的关系，在下一节中大家将会看到如何从正则表达式中构造有穷自动机。但在学习有穷自动机之前，先看一个说明的示例。通过下面的正则表达式可在程序设计语言中给出标识符模式的一般定义（假设已定义了letter 和digit）：identifier = letter ( letter | digit ) *它代表以一个字母开头且其后为任意字母和/ 或数字序列的串。

有穷自动机通过标明数字1 和2 的圆圈表示的是状态（state），它们表示其中记录已被发现的模式的数量在识别过程中的位置。带有箭头的线代表由记录一个状态向另一个状态的转换（transition），该转换依赖于所标字符的匹配。有穷自动机又分为确定型的有穷自动机（DFA）与非确定型的有穷自动机（NFA）两种。

设有正规式r =(a|b)*abb(a|b)*，构造识别该正规集的NFA和最小DFA

首先看一个简单例子R=1的有穷自动机构建：

然后我们再看一个R=1*的例子：

最后再看一个R=01*的例子，其中要注意的是01*的中的1可有可无，1的数量是任意的

那么R

= 01* | 1的有穷自动机就是这个

把这个例子看懂，再结合这题，应该很好解答，L(R) =(a|b)*abb的时候，答案应该是这样的：

时间有限，题主自己扩展求一下，应该还是蛮简单的。

分享题目：有穷自动机java代码 有穷自动机原理
当前URL：http://azwzsj.com/article/ddgshos.html