第二章 形式语言与自动机 Part II自动机

确定有穷自动机的化简 一个有穷自动机是化简了的它没有多余状态并且它的状态中没有两个是互相等价的。 一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。

确定有穷自动机的化简 所谓有穷自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。

确定有穷自动机的化简 两个状态s和t等价： 一致性（兼容性）——同是终态或同是非终态 蔓延性（传播性）——从s出发读入某个aa和从t出发读入某个a到达的状态等价。

DFA的最小化就是寻求最小状态DFA 最小状态DFA的含义: 没有多余状态(死状态) 没有两个状态是互相等价

C和D同是终态,读入a到达C和F, C和F同是终态, C和F读入a都到达C,读入b都到达E. C和D等价 S b a a b F

最小状态DFA 对于一个DFA M =（K,∑,f, k0,,kt)，存在一个最小状态DFA M’ =（K’,∑,f’, k0’,,kt’)，,使L(M’)=L(M). 结论 接受L的最小状态有穷自动机不计同构是唯一的。

把一个DFA的状态分成一些不相交的子集使得任何不同的两子集的状态都是可区别，而同一子集中的任何两个状态都是等价的. “分割法” DFA的最小化算法核心 把一个DFA的状态分成一些不相交的子集使得任何不同的两子集的状态都是可区别，而同一子集中的任何两个状态都是等价的.

DFA的最小化算法 DFA M =（K,∑,f, k0,, kt),最小状态DFA M’ 1.构造状态的一初始划分： 终态kt 和非终态K- kt两组(group) 2.对∏施用过程PP 构造新划分∏new 3. 如∏new =∏,则令 ∏final=∏ 并继续步骤4，否则∏:=∏new重复2 . 4.为∏final中的每一组选一代表，这些代表构成M’的状态。若k是一代表且f(k,a)=t,令r是t组的代表，则M’中有一转换f’(k,a)=r

M’ 的开始状态是含有S0的那组的代表 M’ 的终态是含有F的那组的代表

过程PP : Construction of ∏new For each group G of ∏ do begin 1.Partiton G into subgroups such that two states s and t of G are in the same subgroups if and only if for all input symbols a, states s and t have transitions on a to states in the same group of ∏;/*at worst, a state will be in a subgroup by itself*/ 2.replace G in ∏new by the set of all subgroups formed end

∏0:{S,A,B} {C,D,E,F} ∏1:{S,A,B} {C,D,E,F} ∏2: DFA的最小化—例子 a C D B A E F

正规表达式与有限自动机的等价性 定理 设r是上一个正规表达式，则存在一个FA M接受L( r )。反之亦然。

对于上任一NFA m，能构造上一个正规表达式r，使得L( r )=L(m)。 把转换图的概念拓广，每条弧上可以用一个正规式标记。首先，在m的转换图上加进x,y两个结点。从x用弧连接到m的所有初态结点，从m的所有接受态结点用弧连接到y，从而构成一个新的NFA m’，L(m)=L(m’)。 下面，逐步消去NFA m’中的状态结点，直至剩下x,y为止。在消结的过程中，逐步用正规式标记弧。消结的过程是直观的，只需反复使用下面的替换规则：

替换规则 r1r2 r1 r2 a c a b c 代之以 r1 r1r2 a c a c 代之以 r2 r2 r3 r1 r1r2*r3 a b c a c 代之以

examples

正规表达式=>有限自动机 归纳法

设r具有零个运算，则或r=或r= 或r=a  q0 q1 a r= r=  r=a

设结论对少于i(i1)个运算的正规表达式r成立。当r有i个运算时，有三种情况： 情况1 r=r1r2 情况2 r=r1r2 情况3 r=r1* 有 m1=(1,Q1,q1,F!,1), m2=(2,Q2,q2,F2,2) 且L(m1)=L( r 1), L(m2)=L(r2) ，由m1和m2构造m,使得 L(m)=L( r ).构造方法图示如下：

m1 q1 f1   q0 f0  m2  q2 f2 r=r1r2

 m2 m1 q1 f1 q2 f2  r=r1r2   q0 q1 f1 f0  r=r1* 上述证明方法，是对于一个正规表达式r,构造一个FA m,且L(m)=L( r )的算法,但假定知道r的计算顺序。

例.构造与下列正规式 r=01*1 等价的有限自动机。 q0 q1 q2 q3 1 q2 q3 q5 q4 1 

1 q0 q1 q2 q5 q4  q3 q6 q7 1  q0 q1 q4 q2 q3 q6 q7 1 q8 q5 q9

“语法制导”法---P68

R=(a|ab)* b b*

以上是自动机与正规式的等价。 下面介绍正规文法与自动机的等价性。

文法——自动机 正规文法与有限自动机(FA)的等价性 L(G)=L(m) 定理 对于每一个右线性正规文法或左 线性正规文法G，都存在一个FA m，使 L(m)=L(G)

右线性正规文法 给定右线性正规文法G=(VT,VN,S,P),设 f VN ，令m=(K , VT , , S, Z), 其中，Z= f K= VNf, 转移函数  定义如下： (a) Aa, (A,a)=f (b) A aA1aA2 ... aAn (A,a)= A1,A2 ,... ,,An 

G［Ｓ］： S→aA|bB A→bB|aD|a B→aA|bD|b D→aD|bD|a|b B A S a b a,b D Z 

自动机——文法 定理 对于每一个DFA m，都存在一个右线性正规文法G和一个左线性正规文法G’， 使L(m)=L(G)=L(G’)。

补充说明 关于-FA——FA

消除-FA中边 1）在-FA中寻找边：A ——>B,并且B没有边指向A，此时转2），否则转4）； 2）设状态B的直接后继状态为S1,S2,…,Sk，且 A ——>B ai——>Si 则消除原边，引进新边A ai——>Si ，消去边后，如果BZ则A也应为终态，若A为初态，则B也应为初态. 3）重复2），直到1）中指出边的被消除； 4）对于有回路的情况，则将回路中的状态合并为一个结点。

Summary 正规文法 正规表达式 FA

作业 4(a) 8 9