有限自动机 (Finite Automata)
描述程序设计语言中的单词的识别过程。
主要内容：
? 确定有限自动机 DFA(Deterninistic FA)
? 确定有限自动机 DFA的实现
? 非确定有限自动机 NFA(Nondeterninistic FA)
?NFA到 DFA的转换
?DFA的化简
确定有限自动机 DFA
? 确定有限自动机 DFA为一个五元组
(?,SS,S0,f,TS),其中：
??是一个有穷字母表，它的每个元素称为一个
输入字符；
?SS是一个有穷集，它的每个元素称为一个状态；
?S0? SS是唯一的一个初始状态；
?f是在 SS ? ?? SS上的转换函数
?TS?SS,是一个终止状态集，又称为接受状态
集
DFA的两种表示方式
? 状态转换图：
结点表示状态，转换边表示转换函数，边
的箭头方向指向转换函数中定义的转换方
向。标识出初始状态和终止状态。
? 状态转换表：
可用二维数组描述。标识出初始状态和终
止状态。
Trans（ SI, a）＝ SJ
一个 DFA的例子
? DFA M=( {a,b},{S,U,V,Q},S,f,{Q} ),
? 其中 f 定义为：
f ( S,a )=U f ( V,a )=U
f ( S,b )=V f ( V,b )=Q
f ( U,a )=Q f ( Q,a )=Q
f ( U,b )=V f ( Q,b )=Q
S
U
V
Q
a
b
b a
b
a
a,b
状态转换图
字符
状态 a b
S U V
U Q V
V U Q
Q Q Q
状态转换表
DFA接受的字符串
? 对于 ?*中的任何字符串 t,若存在一条从初始
结点到某一终止结点的路径, 且这条路上所
有弧的标记符连接成的字符串等于 t,则称 t
可为 DFA M所 接受（识别） 。
?DFA M 所能接受的字符串的全体记为 L(M).
DFA的确定性
? 初始状态唯一。
? 转换函数 f:SS???SS是一个单值函数，也就
是说，对任何状态 S?SS,和输入符号 a ? ?,
f(S,a)唯一地确定了下一个状态。即转换函
数至多确定一个状态。
? 没有空边。即没有输入为 ?（ ?）
DFA的实现 1
? 状态转换表的形式,（数组 T存放转换函数）
1.当前状态 State置为初始状态
2.读一个字符 ? CurrentChar
3.如果 CurrentChar?Eof并且
T(State,CurrentChar)?error
则当前状态转为新的状态 T(State,Current)，
读下一字符。重复第 3步工作。
4.如果当前字符为 Eof并且当前状态属于终止状态，
则接受当前字符串，程序结束。否则报错
? 特点：
程序短小，但占用存储空间多
b
DFA的实现 2
? 状态转换图的形式：
? 每个状态对应一个带标号的 case语句
? 转向边对应 goto语句
? 特点：
程序长，但占用存储空间少
i
j
k
a Li,case CurrentChar of
a, goto Lj
b, goto Lk
other, Error( )
非确定有限自动机 NFA
? 定义 1,一个非确定有限自动机 (NFA)A是
一个五元组 A=(?,SS,S0,f,TS).其中
? ?是字母表
? SS是状态集
? S0是初始状态集
? f是转换函数，但不要求是单值的
? f,SS ? (?∪ {?}) ? 2SS
? TS是终止状态集
非确定有限自动机 NFA
? 定义 2,设 A是一个 NFA,A= (?,SS,S0,f,TS)
? 则定义 L(A)为从任意初始状态到任意终止状
态所接受的字符串。
L(A)={?|s0??s’,s0?S0 s’?TS}
? 定义 3,设 A1和 A2是同一个字母表上的自动机，
如果有 L(A1)=L(A2),则称 A1和 A2等价。
NFA到 DFA的转换
? 定理 对于每一个非确定自动机 A,存在一个
确定自动机 A’,使得 L(A)=L(A’).
? 转换,
符号合并
同一状态的不同输出边标有相同的字符。
?合并
含有 ?边
NFA到 DFA的转换
? 符号合并, A,NFA,A’:DFA
1.令 A’的初始状态为 S0’=[S1,S2,… Sk],
其中 S1… Sk是 A的全部初始状态。
2.若 S’=[S1,…,Sm]是 A’的一个状态，
a??则定义
f’(S’,a)=f(S1,a)?f(S2,a)… ?f(Sm,a)
3.若 S’=[S1,…,Sn]是 A’的一个状态,且存
在一个 Si是 A的终止状态，则令 S’为 A’
的终止状态。
NFA到 DFA的转换
? ?合并 （ Close(S)）
1.对 S状态寻找 ?边，如果有令 Ss＝ {S}
2.对任意状态 Si?Ss,如果有,f(Si,?)=Sj则
消除 ?边,Ss= Ss?Sj
重复上述操作直至没有 ?边
3.对 a?? f(Ss,a)= ? f(Sk,a)
Ss={S1,…,Sm},k=1,…,m.
4.如果 Ss中包含 初始状态则 Ss也为初始状
态，如果有终止状态，则 Ss为终止状态。
NFA到 DFA的转换
NFA到 DFA的转换过程,
1,NFA初始状态集的 ?合并集作为 DFA的初始状
态。
2,对 DFA中一状态 S,对 a??,进行符号合并和
?合并得到的状态设为 S’,定义 DFA的转换函
数为 f(S,a)=S’.
3,直至没有新状态产生为止。
例：将如下的 NFA转化为 DFA
bb
b
a
a
?
?
?
?
?
?
?
?0 1
2
4
3
5
6 7 8 9 10
DFA的化简（极小化）
? 状态等价
对 DFA中的两个状态 S1和 S2，
如果将它们看作是初始状态，所接受
的符号串相同，则定义 S1和 S2是等价的。
? 方法
状态合并法
状态分离法
DFA的化简
? 状态合并法（状态吸收方法）
寻找等价状态 S1和 S2
如果 S2为初始状态，则 S1和 S2对调
S2的出现修改为 S1
删除状态 S2。
? 状态分离法
初始化为两个不等价状态集组：非终止状态
组和终止状态组。
对每组中的某个状态分离出与之不等价的状
态组，直至所有状态组内部状态都等价为止
正则表达式与有限自动机等价
定理,对任一确定有限自动机 A,存在一正
则表达式 e,使得 L(A)=L(e),反之亦然。
关系图：
DFA 正则表达式
NFA
正则表达式到 FA的转换规则,
1 3
a b
1 2
a | b
1 3b
*
1 2 3
a b
1 2
a
b
1 2 3
?
b
?
?首先扩展转换图,X W?
1 2 3
a b
1 2
a
b
1 2 3
1 3
a b
1 2
a | b
1 3
a b* ca b c
DFA到正则表达式的转换规则,
词法分析器的工作过程
词法分析器（ Scanner）
输入流
词法描述（正则表达式）
NFA
DFA
TokenList
error
词法分析器的设计
? 人工构造词法分析器过程：
1.确定词法分析器的接口，即确定词法分析
器是作为语法分析的一个子程序还是作为
独立一遍。
2.确定单词分类和 Token结构。
3.根据 2步，构造每一类单词的描述
正则表达式 ?NFA?DFA。
4.根据 3步设计算法实现 DFA。
? 利用工具自动生成,ScanGen Lex
词法分析器的生成器－ Lex
? 功能：
依据语言的正则表达式，自动生成该语言的
词法分析程序。
? 执行过程：
正则
表达式
文件
Lex.l
Lex
词法
分析器
lexyy.c
C编译器
a.out输入流 Token
序列
Lex中的元字符
? [abc], 字符 a,b或 c中的任一个。
? a?, 一个可选的 a。
? [^ab], 除了 a,b外的任何一个字符。
?,, 除了新行之外的任一字符。
? \., 字符,,”。
? {xxx},名字为 xxx的正则表达式。
? [a-z], a到 z中的任一字符。
为了与减号区别，减号表示为,\-”。
Lex输入文件的格式
? 输入文件格式：
{declarations}
%%
{rules}
%%
{auxiliary procedures}
%{声明变量,常量 %}
正则定义
p {action}
例子
%{
LT,LE,IF,THEN,ELSE
#include <stdio.h>
int count =0;
%}
letter [A-Za-z]
digit [0-9]
id {letter} ({letter}| {digit})*
%%
if {return (IF);}
{id} {yylval = installid();return (ID);}
“<” {yylval = LT; return (RELOP);}
%%
installid()
{ …… }
单元总结
?两个工具：
有限自动机、正则表达式
?三个算法：
正则表达式到 FA的转换
NFA到 DFA的转换
DFA的化简
?一个实现：
DFA的实现
作业：
? 构造正则表达式 (a|b)*abb(a|b)*的最简
DFA。要求先构造 NFA，其次转换为 DFA，最
后加以极小化。
? 书上 Pp58 第 8题
附加题：
? 分别构造 {?}和 ?的自动机
描述程序设计语言中的单词的识别过程。
主要内容：
? 确定有限自动机 DFA(Deterninistic FA)
? 确定有限自动机 DFA的实现
? 非确定有限自动机 NFA(Nondeterninistic FA)
?NFA到 DFA的转换
?DFA的化简
确定有限自动机 DFA
? 确定有限自动机 DFA为一个五元组
(?,SS,S0,f,TS),其中：
??是一个有穷字母表，它的每个元素称为一个
输入字符；
?SS是一个有穷集，它的每个元素称为一个状态；
?S0? SS是唯一的一个初始状态；
?f是在 SS ? ?? SS上的转换函数
?TS?SS,是一个终止状态集，又称为接受状态
集
DFA的两种表示方式
? 状态转换图：
结点表示状态，转换边表示转换函数，边
的箭头方向指向转换函数中定义的转换方
向。标识出初始状态和终止状态。
? 状态转换表：
可用二维数组描述。标识出初始状态和终
止状态。
Trans（ SI, a）＝ SJ
一个 DFA的例子
? DFA M=( {a,b},{S,U,V,Q},S,f,{Q} ),
? 其中 f 定义为：
f ( S,a )=U f ( V,a )=U
f ( S,b )=V f ( V,b )=Q
f ( U,a )=Q f ( Q,a )=Q
f ( U,b )=V f ( Q,b )=Q
S
U
V
Q
a
b
b a
b
a
a,b
状态转换图
字符
状态 a b
S U V
U Q V
V U Q
Q Q Q
状态转换表
DFA接受的字符串
? 对于 ?*中的任何字符串 t,若存在一条从初始
结点到某一终止结点的路径, 且这条路上所
有弧的标记符连接成的字符串等于 t,则称 t
可为 DFA M所 接受（识别） 。
?DFA M 所能接受的字符串的全体记为 L(M).
DFA的确定性
? 初始状态唯一。
? 转换函数 f:SS???SS是一个单值函数，也就
是说，对任何状态 S?SS,和输入符号 a ? ?,
f(S,a)唯一地确定了下一个状态。即转换函
数至多确定一个状态。
? 没有空边。即没有输入为 ?（ ?）
DFA的实现 1
? 状态转换表的形式,（数组 T存放转换函数）
1.当前状态 State置为初始状态
2.读一个字符 ? CurrentChar
3.如果 CurrentChar?Eof并且
T(State,CurrentChar)?error
则当前状态转为新的状态 T(State,Current)，
读下一字符。重复第 3步工作。
4.如果当前字符为 Eof并且当前状态属于终止状态，
则接受当前字符串，程序结束。否则报错
? 特点：
程序短小，但占用存储空间多
b
DFA的实现 2
? 状态转换图的形式：
? 每个状态对应一个带标号的 case语句
? 转向边对应 goto语句
? 特点：
程序长，但占用存储空间少
i
j
k
a Li,case CurrentChar of
a, goto Lj
b, goto Lk
other, Error( )
非确定有限自动机 NFA
? 定义 1,一个非确定有限自动机 (NFA)A是
一个五元组 A=(?,SS,S0,f,TS).其中
? ?是字母表
? SS是状态集
? S0是初始状态集
? f是转换函数，但不要求是单值的
? f,SS ? (?∪ {?}) ? 2SS
? TS是终止状态集
非确定有限自动机 NFA
? 定义 2,设 A是一个 NFA,A= (?,SS,S0,f,TS)
? 则定义 L(A)为从任意初始状态到任意终止状
态所接受的字符串。
L(A)={?|s0??s’,s0?S0 s’?TS}
? 定义 3,设 A1和 A2是同一个字母表上的自动机，
如果有 L(A1)=L(A2),则称 A1和 A2等价。
NFA到 DFA的转换
? 定理 对于每一个非确定自动机 A,存在一个
确定自动机 A’,使得 L(A)=L(A’).
? 转换,
符号合并
同一状态的不同输出边标有相同的字符。
?合并
含有 ?边
NFA到 DFA的转换
? 符号合并, A,NFA,A’:DFA
1.令 A’的初始状态为 S0’=[S1,S2,… Sk],
其中 S1… Sk是 A的全部初始状态。
2.若 S’=[S1,…,Sm]是 A’的一个状态，
a??则定义
f’(S’,a)=f(S1,a)?f(S2,a)… ?f(Sm,a)
3.若 S’=[S1,…,Sn]是 A’的一个状态,且存
在一个 Si是 A的终止状态，则令 S’为 A’
的终止状态。
NFA到 DFA的转换
? ?合并 （ Close(S)）
1.对 S状态寻找 ?边，如果有令 Ss＝ {S}
2.对任意状态 Si?Ss,如果有,f(Si,?)=Sj则
消除 ?边,Ss= Ss?Sj
重复上述操作直至没有 ?边
3.对 a?? f(Ss,a)= ? f(Sk,a)
Ss={S1,…,Sm},k=1,…,m.
4.如果 Ss中包含 初始状态则 Ss也为初始状
态，如果有终止状态，则 Ss为终止状态。
NFA到 DFA的转换
NFA到 DFA的转换过程,
1,NFA初始状态集的 ?合并集作为 DFA的初始状
态。
2,对 DFA中一状态 S,对 a??,进行符号合并和
?合并得到的状态设为 S’,定义 DFA的转换函
数为 f(S,a)=S’.
3,直至没有新状态产生为止。
例：将如下的 NFA转化为 DFA
bb
b
a
a
?
?
?
?
?
?
?
?0 1
2
4
3
5
6 7 8 9 10
DFA的化简（极小化）
? 状态等价
对 DFA中的两个状态 S1和 S2，
如果将它们看作是初始状态，所接受
的符号串相同，则定义 S1和 S2是等价的。
? 方法
状态合并法
状态分离法
DFA的化简
? 状态合并法（状态吸收方法）
寻找等价状态 S1和 S2
如果 S2为初始状态，则 S1和 S2对调
S2的出现修改为 S1
删除状态 S2。
? 状态分离法
初始化为两个不等价状态集组：非终止状态
组和终止状态组。
对每组中的某个状态分离出与之不等价的状
态组，直至所有状态组内部状态都等价为止
正则表达式与有限自动机等价
定理,对任一确定有限自动机 A,存在一正
则表达式 e,使得 L(A)=L(e),反之亦然。
关系图：
DFA 正则表达式
NFA
正则表达式到 FA的转换规则,
1 3
a b
1 2
a | b
1 3b
*
1 2 3
a b
1 2
a
b
1 2 3
?
b
?
?首先扩展转换图,X W?
1 2 3
a b
1 2
a
b
1 2 3
1 3
a b
1 2
a | b
1 3
a b* ca b c
DFA到正则表达式的转换规则,
词法分析器的工作过程
词法分析器（ Scanner）
输入流
词法描述（正则表达式）
NFA
DFA
TokenList
error
词法分析器的设计
? 人工构造词法分析器过程：
1.确定词法分析器的接口，即确定词法分析
器是作为语法分析的一个子程序还是作为
独立一遍。
2.确定单词分类和 Token结构。
3.根据 2步，构造每一类单词的描述
正则表达式 ?NFA?DFA。
4.根据 3步设计算法实现 DFA。
? 利用工具自动生成,ScanGen Lex
词法分析器的生成器－ Lex
? 功能：
依据语言的正则表达式，自动生成该语言的
词法分析程序。
? 执行过程：
正则
表达式
文件
Lex.l
Lex
词法
分析器
lexyy.c
C编译器
a.out输入流 Token
序列
Lex中的元字符
? [abc], 字符 a,b或 c中的任一个。
? a?, 一个可选的 a。
? [^ab], 除了 a,b外的任何一个字符。
?,, 除了新行之外的任一字符。
? \., 字符,,”。
? {xxx},名字为 xxx的正则表达式。
? [a-z], a到 z中的任一字符。
为了与减号区别，减号表示为,\-”。
Lex输入文件的格式
? 输入文件格式：
{declarations}
%%
{rules}
%%
{auxiliary procedures}
%{声明变量,常量 %}
正则定义
p {action}
例子
%{
LT,LE,IF,THEN,ELSE
#include <stdio.h>
int count =0;
%}
letter [A-Za-z]
digit [0-9]
id {letter} ({letter}| {digit})*
%%
if {return (IF);}
{id} {yylval = installid();return (ID);}
“<” {yylval = LT; return (RELOP);}
%%
installid()
{ …… }
单元总结
?两个工具：
有限自动机、正则表达式
?三个算法：
正则表达式到 FA的转换
NFA到 DFA的转换
DFA的化简
?一个实现：
DFA的实现
作业：
? 构造正则表达式 (a|b)*abb(a|b)*的最简
DFA。要求先构造 NFA，其次转换为 DFA，最
后加以极小化。
? 书上 Pp58 第 8题
附加题：
? 分别构造 {?}和 ?的自动机
