第三章 有穷自动机.doc

第三章 有穷自动机.doc第三章有穷自动机
1、教学目的及要求:
本章介绍有关有穷自动机的基本概念和理论以及正规文法、正规表达式与有穷自动机之间的相互关系。要求掌握正则文法、状态转换图、DFA、NFA、正规式和正规集的基本概念。
2、教学内容:
本章介绍有关有穷自动机的基本概念和理论以及正规文法、正规表达式与有穷自动机之间的相互关系。
3、教学重点:
状态转换图。
4、教学难点:
◇正规式的定义-如何用作单词的描述工具
◇有穷自动机的定义和分类-如何用作单词的识别系统
◇正规式到有穷自动机的转换算法-词法分析程序的自动构造原理
◇正则文法、正规集、DFA、NFA的相互转化。
5、课前思考
◇什么是有穷自动机?
◇什么是状态转换图?
6、章节内容
第一节有穷自动机的形式定义
第二节 NFA到DFA的转换
第三节正规文法与有穷自动机
第四节 正规表达式与FA
第五节 DFA在计算机中的表示
有穷自动机的形式定义
有穷状态自动机(Finite-state Automata 或简称FA)在识别功能上与正规文法类等价,而且也等价于一个特殊类型的语言产生器——正规表达式(Regular Expression)。因此许多简单的程序语言都可由FA所识别。事实上,它是描述词法的有效工具,也是进行词法分析的主要理论基础。
为了构造词法分析程序,要研究构词法,每种词类的结构模式以及识别它的数学模型——有穷自动机。它的模拟程序可以作为词法分析程序的控制程序。
有穷自动机(也称有限自动机)作为一种识别装置,它能准确地识别正规集,即识别正规文法所定义的语言和正规式所表示的集合,引入有穷自动机这个理论,正是为词法分析程序的自动构造寻找特殊的方法和工具。
有穷自动机分为两类:确定的有穷自动机(Deterministic Finite Automata)和不确定的有穷自动机(Nondeterministic Finite Automata) 。
一、确定有穷自动机的形式定义
一个确定的有穷自动机 M(记作DFA M)是一个五元组M=(K,Σ,f,S,Z),其中
(a) K是一个有限状态集合。
(b) Σ是一个字母表,它的每个元素称为一个输入字符。
(c) SÎK,S 称为初始状态,唯一。
(d) ZÌK, Z称为终态集合, 终态也称可接受状态或结束状态。
(e) f是转换函数,是一个从K×Σ到K的单值映射。f(ki,a)=kj(ki,kjÎQ,aÎΣ)kj称为ki的一个后继状态。
确定性的体现:初始状态唯一; 转换函数为单值映射。
例: 设DFA M=({S,U,V,Q},{a,b},f,S,{Q})其中
     f(S,a)=U, f(S,b)=V
     f(U,a)=Q, f(U,b)=V
     f(V,a)=U, f(V,b)=Q
     f(Q,a)=Q, f(Q,b)=Q
因为(1)初始状态唯一是S,(2)每个转换函数均为单值映射。所以该FA为确定有穷自动机。
二、状态转换表
DFA的映射关系可以由一个矩阵表示,矩阵的行标表示状态,列标表示输入字符,矩阵元素表示f(s,a)的值,这个矩阵称为状态转换表。
例:
a
b
S
U
V
U
Q
V
V
U
Q
Q
Q
Q
f(S,a)=U      f(S,b)=V
    f(U,a)=Q     f(U,b)=V
    f(V,a)=U     f(V,b)=Q
    f(Q,a)=Q     f(Q,b)=Q
q1
a
a
a
b
b
a
b
b
q2
q3
q0
三、状态转换图
图中标有Þ的为开始状态,标有双圈的状态为终止状态。
若f(Ki,a)=Kj,则从状态结点Ki到状态Kj画标记为a的弧。
四、自动机的等价性
为了讨论自动机的等价性,先对DFA中的映射进行扩充。
1、扩充的转换函数f
(1)设QÎK,函数f(Q,ε)=Q,即如果输入字符是空串,则仍停留在原来的状态上。
(2)对"QÎK,TÎΣ,t1ÎΣ*,f(Q,Tt1)=f(f(Q,T), t1) 该定义是一个递归定义,说明当自动机处在状态Q且面临某个输入串Tt1时,则首先应用函数 f(Q,T)=P,然后应用函数f(P,t1)。
DFA的确定性表现在转换函数f: K×Σ→K是一个单值函数,即对任何状态kÎK和输入符号aÎΣ,f(k,a)唯一地确定了下一个状态,从状态转换图来看,若字母表Σ含有n个输入字符,那么任何一个状态结点最多有n条弧射出,且每条弧以一个不同的输入字符标记。
2、自动机接受字符串x:
如果对于某一自动机M=(K,Σ,f,S,Z),xÎΣ*,有f(S