编译原理学习笔记（三）：有限自动机_有限自动机例题

自动机基础

简介：自动机是一种语言模型，是一种语言的识别工具，其中的有限自动机（Finite Automata,FA）被用来处理正规语言，正规语言是编译程序设计中此法分析的对象。

正规语言及其描述方法
正规语言的定义
【定义】正规语言是指由正规文法定义的语言，程序设计语言的单词大都属于此种语言。

正规文法仅有三种形式的产生式：
（1）A->aB （2）A->a （3）A->ε

正规语言有三种等价的表示方法：
（1）正规文法 （2）正规式 （3）有限自动机

正规语言的判定事例:

正规语言的另外两种表示方法：

事例

三种方法描述：

注意：凡是能由上述方法的一种表示的语言，一定是正规语言，反之一定不是正规语言。

有限自动机的定义和分类

有限自动机的等价转换

有限自动机的实现

用计算机完成有限自动机的功能，核心是“变换”的技术，这里介绍的是把变换表按某种方式存储起来作为知识源识别单词。

实现机制：控制程序+变换表

说明：

（1）假设自动机只作为识别器则对待识别的字符串只回答是或否.
（2）可令#作为待识别符号串的后继符。如图所示：

（3）令getchar(ch)为读符号函数。

变换表存储结构设计

1.二维数组:通常采用连续的正整数。
2.压缩变换表：把每个状态行作为子表，状态作为索引，如图：

有限自动机实现事例

输入aacd#识别过程

压缩变换表：

正规语言描述方法间的相互转换

正规语言有三种等价的表示方法:
(1)正规文法 (2)正规式 (3)有限自动机

这里我们只介绍正规文法与有限自动机、正规式与有限自动机的关系。
正规文法：四元组
有限自动机：五元组

两个事例:
例题一：【自动机=>正规文法】

转换步骤：令Z-① , A-② , B-③,则有正规文法：
G（Z）： Z->aA|cB A->bA|dB B->ε

例题二：【正规文法=>自动机，并求L（G）】

正规文法：Z->aZ|bA|ε,A->bA|d

转换步骤：A->d可以变换为A->dB,B->ε,所以G^(Z)与G（Z）等价，
则有G ^(Z)：Z->aZ|bA|ε A->bA|dB B->ε

自动机如图所示：

L(G)如图所示：

正规式转换为有限自动机：

解释：
I：将【|】符号拆开，分成两条路。
II:将ab,bc分别拆开，增加两个状态:② ③,分成四条路。
III:分解两个星闭包。删除①，② 的ε边。
IV:删除 ③，⑨的ε边，添加①③的b边。
V:删除 ③，⑨的边。
VI:确定化过程，将①，②状态命名为A，看它经过a,b,c能够变化到哪样的状态集合，以此类推，再出现4个新的状态BCDE。
比如：遇见a时，到达②状态，将②状态命名为B，遇见b时到达结束状态…