第二章 词法分析2 确定有限自动机DFA 确定有限自动机（DFA）的定义 DFA的两种表示方法 DFA接受的集合 DFA的确定性 自动机的实现

2.4 有限自动机FA（Finite Automata ) 有限自动机FA作为一种识别装置，它能准确识别正规集。引入FA这个理论，正是为词法分析程序的自动构造寻找一种特殊的方法和工具。 确定有限自动机（DFA： Deterministic Finite Automata ) 非确定有限自动机（NFA： Nondeterministic Finite Automata )

(一） 确定有限自动机DFA的定义 确定有限自动机M为一个五元组: M = ( S , , f , s0 , Z )，其中： 是一个有穷字母表，它的每个元素称为一个输入字符； f是状态转换函数:S S，且单值函数.f(Si,a)=Sk 表示当前状态为Si，遇输入字符a 时，自动机将唯一地转换到状态 Sk，称Sk为 Si的一个后继状态; s0S，是唯一的一个初始状态(开始状态)； ZS，是终止状态集，其中的每个元素称为终止状态（可接受状态、结束状态）,Z可空.

一个DFA的例子 DFA M=({S0, S1, S2, S3} , {a,b}, f , S0 , {S3}), 其中f 定义为： f (S0, a )=S1 f (S2, a )=S1 f (S0, b )=S2 f (S2, b )= S3 f (S1, a )= S3 f (S3, a )= S3 f (S1, b )= S2 f (S3, b )= S3

（二） DFA的两种表示方式 (1) 状态转换图 ：用有向图表示自动机，比较直观，易于理解； (2) 状态转换矩阵：用二维数组描述自动机，易于程序的自动实现；

(1) 状态转换图 ：用有向图表示自动机 1. 结点：表示状态： 1) 非终止状态： 2）终止状态： 3）开始状态： 1) 非终止状态： 2）终止状态： 3）开始状态： 2. 边：表示状态转换函数： Si Sk S0 a f(Si,a)=Sj Si Sj

a a a ,b b a b b 状态转换图 DFA M=( {S0, S1, S2, S3}, {a,b}, f, S0, {S3}), f (S0, a )=S1 f (S2, a )=S1 f (S0, b )=S2 f (S2, b )= S3 f (S1, a )= S3 f (S3, a )= S3 f (S1, b )= S2 f (S3, b )= S3 S1 a a a ,b b a S3 S0 b b S2 状态转换图

 a b (2) 状态转换矩阵：用二维数组描述DFA 行：表示所有的状态; 初始状态：一般约定，第一行表示开始状态， 或在右上角标注“+”； 终止状态:右上角标有“*”或“-” ； 列：表示上的所有输入字符； 矩阵元素：表示状态转换函数.  状态 a b S0+ S1 S2 S3 S3*

DFA M=( {S0, S1, S2, S3}, {a,b}, f, S0, {S3}), 其中 f 定义为： f (S0, a )=S1 f (S2, a )=S1 f (S0, b )=S2 f (S2, b )= S3 f (S1, a )= S3 f (S3, a )= S3 f (S1, b )= S2 f (S3, b )= S3 输入字符 状态 a b S0+ S1 S2 S3 S3*

（三） 陷阱状态 1 2 3 4 设有DFA M=（{0,1,2,3,4},{a,b},f,0,{3}） 其中 f 定义为： f(0,a) = 1 f(0,b) = 4 f(1,a) = 4 f(1,b) = 2 f(2,a) = 3 f(2,b) = 4 f(3,a) = 3 f(3,b) = 3 f(4,a) = 4 f(4,b) = 4 1 2 3 a b a, b a, b a b 4

Σ S a b 0+ 1 2 3 3* 4 4 4 4 4 4 1 2 3 a b a, b

（四） DFA的确定性 初始状态唯一. 状态转换函数f: f是一个单值函数，也就是说，对任何状态sS,和输入符号a,f(s,a)值唯一，即唯一地确定了下一个后继状态。 没有输入为空边，即不接受没有任何输入就进行状态转换的情况。

（五）DFA接受的字符串 对于中的任何字符串a1a2...an,若在DFA M中存在一条从初始结点到某一终止结点的路径，且这条路上所有弧上的标记符连接成的字符串等于a1a2...an,则称该字符串可为DFA M所接受（识别）。 S0 S1 S2 S3 a b S4 aba(ab)* √ aba √ abaa ×  √ abaab √

DFA接受的语言 定义： DFA M所能接受的字符串的全体，称为DFA M 接受(识别)的语言，记为L(M)。

例1：L( M2 )={a, ab, abb, abbb,…} 1 a b DFA M2

例2：L( M3 )={, b, bb, bbb,…} 1 b DFA M3

DFA的应用 在语言学中：自动机作为语言识别器。 在计算机科学中：自动机用作计算机和计算过程的动态数学模型，用来研究计算机的体系结构、逻辑操作、程序设计等。 在自动控制领域内：自动机可作为控制信号序列进行逻辑处理的装置。

例3：试用自动机描绘复印机的工作过程： 复印机启动后进入等候状态。接到复印命令进入复印状态执行复印任务，完成任务后回到等候状态。接到关机命令进入结束状态； 复印机执行复印任务时发现没纸，则进入缺纸状态，发出警告等待装纸，装纸结束后回到等候状态； 复印时发现卡纸，则进入卡纸状态，发出警告等待维修，故障排除后回到等候状态。

复印机工作过程状态转换图 复印 命令 启动 命令 开始 等待 复印 完成 关机 命令 装纸 故障 排除 卡纸 没纸 结束 卡纸 缺纸

例4：设计DFA以识别所有能被3整除 的二进制数的集合. S0: 00 01 S0：余0状态（能被3整除状态） S1：余1状态 S2：余2状态 S1: 10 11 S2: 100 101 1 1 1 S1 S0 S2

设计DFA以识别所有能被3整除的无符号十进制数。 例5 设计DFA以识别所有能被3整除的无符号十进制数。 S0:能被3整除状态 S1：余1状态 S2：余2状态 1 2 0,3,6,9 1,4,7 2,5,8 21

（六） DFA描述单词 标识符的描述 L=a|b|…|z|A|B|…|Z|_ 则有： 1 L表示所有字母与下划线： D表示数字： D=0|1|2|…|9 则有： L|D 上次课我们说了，单词可以分成四类，分别是保留字、标示符、常数、特殊符号（运算符 界限符 格式符），或者说3类把保留字归入特殊符号，下面就看看用自动机怎么描述他们并组成一个大的自动机 L 1

. . . 2 1 5 6 3 4 常数的描述 D=0|1|2|…|9 , D1=1|2|…|9 无符号整数: D1D*|0 举几个例子试试~ 我们看到，画了这些自动机以后，如果输入的字符可以从开始状态出发到达终止状态，并停留在终止状态上，那么这个串就是该自动机可以接受的串，至于说如何来区分他是哪类的单词 这个实际上是很好办的，因为停在不同的终止状态上反映了我们识别的是不同类型的单词。比如停留在2上说明是整数，1上说明是整数，6说明是实数。所以看一个串是否可以接受，看停留状态的类型，看一个它是哪类单词，就看停在哪个终止状态上。 D1 1 . 5 D 6 4 . +|- D1 3

特殊符号 1 { 2 + 3 > 4 = 保留字 特殊符号的单词可能更好画，虽然相对麻烦一点，因为这类的单词是有限的，我们就可以用枚举的方式把这些信息都枚举出来 把所有的都枚举了就行。 注意个问题，一个是到达终止状态后，还要继续读 包括标识符 常数 双目运算符 同时我们的词法分析程序并不是把这些自动机分开画的，而是拼在一起，把他们的初始状态合并成一个。 这个时候会有细心的同学发现+ -号的问题，如果合成一个就区分不出4+5的+5了，所以遇到这种问题的时候要往前看一个符号，来决定当前符号的类型 这是用自动机描述单词，假如开始的时候没有把问题分析清楚，直接做词法分析程序，会很麻烦也很难保证准确性，描述了以后就好办了，剩下就是看怎么实现自动机了 3 f 1 o 2 r 4 i 5

（七） DFA程序实现 编写程序考察输入任意以‘#’结尾的字符串是否可被DFA M识别 DFA实现方法有两种 直接转向法：基于状态转化图 基于状态转换矩阵

方法1：直接转向法 例： 每个状态对应一个带标号的switch语句,转向边对应goto语句 Li: switch ( CurChar ) { case ‘ a’ ： goto Lj; case ‘b’ : goto Lk; case ‘#’ : Accept; default : Error( ); } i j k a b 特点： 程序的结构一样，但程序随着状态图的不同而改变

方法2：基于状态转换矩阵 state=S0; return(true); 特点：程序内容不变，只需改变 curChar=readNextChar(); while(curChar!=‘#’ && T[state,curchar]error) { //则当前状态转为新的状态 state = T[state,curChar]; curChar=readNextChar() ； } if(curChar==‘#’ && state FinalState) return(true); else return(false); 特点：程序内容不变，只需改变 状态表内容，但状态多时占用存储空间大.

练习： 设字母表={x，y，z}， 所有上定义的串。 不包含y的所有符号串集合。 包含偶数个x的所有符号串。