第三章 有穷自动机.pptx

§ 有穷自动机的形式定义
有穷状态自动机(Finite-state Automata 或简称FA)在识别功能上与正规文法类等价,而且也等价于一个特殊类型的语言产生器——正规表达式(Regular Expression)。因此许多简单的程序语言都可由FA所识别。事实上,它是描述词法的有效工具,也是进行词法分析的主要理论基础。
有穷自动机分为两类:
(1)确定的有穷自动机
(Deterministic Finite Automata简称DFA)
(2)不确定的有穷自动机(Nondeterministic Finite Automata简称NFA) 。
确定有穷自动机的形式定义
一个DFA 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∈K,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)的值,这个矩阵称为状态转换表。
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
a
b
S
U
V
U
Q
V
V
U
Q
Q
Q
Q
q1
a
a
a
b
b
a
b
b
q2
q3
q0
状态转换图
图中标有的为开始状态,标有双圈的状态为终止状态。
若f(Ki,a)=Kj,则从状态结点Ki到状态Kj画标记为a的弧。
自动机的等价性
为了讨论自动机的等价性,先对DFA中的映射进行扩充。
扩充的转换函数f
设QK,函数f(Q, )=Q,即如果输入字符是空串,则仍停留在原来的状态上。
对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条弧射出,且每条弧以一个不同的输入字符标记。
自动机接受字符串x
如果对于某一自动机M=(K,,f,S,Z),x*,有f(S,x)=P,且PZ,则x为该自动机M所接受(识别),即自动机从开始状态开始,在读完全部输入串以后,自动机恰恰到达终止状态,则该输入串能被该自动机所接受。
例:DFA M=({S,A,B,C},{0,1},,S,{S}),且定义为(S,0)=B,(S,1)=A,(A,0)=C,(A,1)=S,(B,0)=S, (B,1)=C,(C,0)=A,(C,1)=B
状态图表示,矩阵表示: