形式语言 第3 有穷状态自动机.ppt

* * 3.5.1 FA与左线性文法 按照上面的分析，对应于形如A?Ba的产生式：FA应该在状态B读入a时，将状态转换到A。也可以理解为：在状态B，FA已经将当前句子的、处理过的前缀“归约”成了B，在此时它读入a时，要将Ba归约成A，因此，它进入状态A。 * * 3.5.1 FA与左线性文法 按照“归约”的说法，如果一个句子是文法G产生的语言的合法句子，它最终应该被归约成文法G的开始符号。所以，G的开始符号对应的状态就是相应的FA的终止状态。 如何解决好开始符号只有一个，而DFA的终止状态可以有多个的问题。 * * 3.5.1 FA与左线性文法 例如：对文法 G2：E?A0|B1 A?1|C1 B?0|C0 C?B0|A1 对应 δ(A，0)={E} δ(B，1)={E} δ(Z，1)={A} δ(C，1)={A} δ(Z，0)={B} δ(C，0)={B} δ(B，0)={C} δ(A，1)={C} * * 3.5.1 FA与左线性文法 G2：E?A0|B1 A?1|C1 B?0|C0 C?B0|A1 * * 3.5.1 FA与左线性文法 DFA (的状态转移图)作如下“预处理”： ⑴ 删除DFA的陷阱状态(包括与之相关的弧)； ⑵ 在图中加一个识别状态； ⑶ “复制”一条原来到达终止状态的弧，使它从原来的起点出发，到达新添加的识别状态。 * * 3.5.1 FA与左线性文法 ⑴ 如果δ(A，a)=B，则有产生式B?Aa； ⑵ 如果δ(A，a)=B，且A是开始状态，则有产生式B?a。 定理3-5 左线性文法与FA等价。 练习 构造下图所给DFA对应的右线性文法和左线性文法 S q0 q1 q2 q3 0 0 1 0,1 0 1 1 q0 q1 q2 q3 S 1 1 1 0 0 0，1 练习 根据所给文法，构造相应的FA 1）S?a|aA A?a|aA|cA|bB B?a|b|c|aB|bB|cB 2）S?a|Aa A?a|Aa|Ac|Bb B?a|b|c|Ba|Bb|Bc * * 3.6 FA的一些变形 3.6.1 双向有穷状态自动机 确定的双向有穷状态自动机(two-way deterministic finite automaton，2DFA) M=(Q，∑，δ，q0，F) Q、∑、q0、F的意义同DFA。 * * 3.6.1 双向有穷状态自动机 δ：Q×∑?Q×{L，R，S}，对?(q，a)∈Q×∑ 如果δ(q，a)= {p，L}，它表示M在状态q读入字符a，将状态变成p，并将读头向左移动一个带方格而指向输入字符串的前一个字符。 如果δ(q，a)= {p，R}，它表示M在状态q读入字符a，将状态变成p，并将读头向右移动一个带方格而指向输入字符串中下一个字符。 如果δ(q，a)= {p，S}，它表示M在状态q读入字符a，将状态变成p，读头保持在原位不动。 * * 3.6.1 双向有穷状态自动机 例 一个2DFA M,行为如下：从状态q0出发，M重复下述动作循环，读头向右移动直到遇到两个1，然后左移直到遇到一个0，这时，M又重新进入状态q0 ，并重复这个循环。M有三个状态，都是终止状态。考虑输入101001。 状态 输入字符 0 1 q0 (q0,R) (q1,R) q1 (q1,R) (q2,L) q2 (q0,R) (q2,L) * * 3.6.1 双向有穷状态自动机 M接受的语言 L(M)={x| q0x├*xp且p∈F} 是2DFA接受的语言。 定理3-6 2DFA与FA等价。 * * 3.6.1 双向有穷状态自动机 不确定的双向有穷状态自动机(two-way nondeterministic finite automaton，2NFA) M=(Q，∑，δ，q0，F) Q、∑、q0、F的意义同DFA。 δ：Q×∑?2Q×{L，R，S} 。 * * 3.6.1 双向有穷状态自动机 δ(q，a)= {( p1，D1)( p2，D2) …，(pm,Dm) }表示M在状态q读入字符a，可以选择地将状态变成p1同时按D1实现对读头的移动、或者将状态变成p2同时按D2实现对读头的移动、……或者将状态变成pm同时按Dm实现对读头的移动。其中D1，D2，…，Dm∈{L，R，S}，表示的意义与2DFA的定义表示的意义相同。 * * 3.6.1 双向有穷状态自动机 定理3-7 2NFA与FA等价。 * * 3.6.2 带输出的FA Moore机 M=(Q，∑，Δ，δ，λ，q0) Q、∑、q0、δ的意义同DFA。 Δ——输出字母表(output alphabet)。 λ：Q?Δ为输出函数。对?q∈Q，λ