第二章 形式语言与自动机理论基础(有限自动机).ppt

NFA M=(S,?,f,S0,Z) ?等价的DFA M’=(S’,?’,f’,S0’,Z’) S’=2S (由NFA M的状态集S的所有子集组成) Z’={K|K ∈S’且K≤ Z≠ ?} （Z’是由至少包含Z中一个状态S的所有子集组成） S0’={S0} ?’= ? f’(K,a)=P, 其中K,P∈S’ 且 P={p|p∈f(q,a),q∈k} DFA M’ 的f’: f’({k1,k2,…ki},a)={p1,p2,…pi} 当且仅当 NFA M 的f: f({k1,k2,…ki},a)={p1,p2,…pi} 证明 （略P30） 关系图： 关系图： 3、闭包运算 r=r1* q0 f0 ? ? ? ? q1 f1 r=r1* m1 start 例 构造与 r=1* 等价的有限自动机。 q1 q2 1 q1 q2 q4 q3 1 ? ? ? ? start r=r1* q0 f0 ? ? ? ? q1 f1 m1 start 例 构造与 r=01* 等价的有限自动机。 q1 q2 q4 q3 1 ? ? ? ? start q1 q2 0 q1 f1 q2 m2 m1 f2 ? r=r1r2 start 0 q0 q1 ? q3 q4 q5 q2 1 ? ? ? ? start q0 q1 f1 f2 q2 f0 m2 m1 ? ? ? ? r=r1?r2 start 例 构造与 r=01*?1 等价的有限自动机。 0 q0 q1 ? q3 q4 q5 q2 1 ? ? ? ? start q1 q2 1 q6 q7 1 q8 q9 ? ? ? ? 0 q0 q1 ? q3 q4 q5 q2 1 ? ? ? ? start ? ? 3 letter 1 2 ? 4 5 letter 6 ? 7 8 digit ? ? 9 ? 10 ? ? start letter(letter|digit)* 2 letter letter 0 digit start 正规表达式 NFA DFA 最小化 化简过程 ? ? 3 letter 1 2 ? 4 5 letter 6 ? 7 8 digit ? ? 9 ? 10 ? ? start letter {1} start {2,3,4,5,7,10} {4,5,6,7,9,10} {4,5,7,8,9,10} letter digit digit letter letter digit 2 letter letter 0 digit start 对于?上任一正规表达式r ，一定能构造一个NFA m ，使得L( r )=L(m)。 首先对NFA m构造一个广义的转换图，其中只有开始状态S和终止状态Z，连接S和Z的有向弧上是正规式R，然后按照下面的替换规则对正规式不断进行分解，不断加入状态结点和箭弧，直到转换图上的所有弧标记都是?上的元素或?为止。 2. 转换法证明正规式与有限自动机的等价 a c a c a c r1r2 r1?r2 r1r2*r3 替换规则 代之以 代之以 代之以 a b c a c a b c r1 r2 r2 r2 r1 r1 r3 从正规式到有限自动机 设?={x,y}, ?上的正规式R=xy*(xy|yx)x*，构造一个NFA M，使L(M)=L(R). xy*(xy|yx)x* S Z start x S Z 1 y* 2 xy|yx 3 x* x S Z 1 ? 3 xy 4 2 ? y yx ? 5 ? x x S Z 1 ? 3 x 6 2 ? y y ? 7 ? x y x 4 5 3 letter 1 2 ? 4 ? 5 letter 6 ? ? 7 8 digit ? ? 9 ? 10 ? ? start letter(letter|digit)* 2 3 letter letter 0 digit start ? 1 ? 构造法 转换法 NFA？ 正规表达式 NFA DFA 最小化 化简过程 构造法 转换法 对于?上任一NFA m，能构造?上一个正规表达式r，使得L( r )=L(m)。 把转换图的概念拓广，每条弧上可以用一个正规式标记。首先，在m的转换图上加进S,Z两个结点。从S用?弧连接到m的所有初态结点，从m的所有终结（接受）结点用?弧连接到Z，从而构成一个新的NFA m’，L(m)=L(m’)。 反复使用下面的替换规则逐步消去NFA m’中的状态结点和弧，直至剩下S,Z为止。在消去结点的过程中，逐步用正规式标记弧。 从正规式到有限自动机 从有限自动机到正规式 构造法 转换法 a b c a