自动机与形式语言第三章 epsilon_NFA.ppt

* * * * * * * * * 3.5.1 FA与右线性文法 定理3-4 正则语言可以由FA接受。 证明： （1）构造。 基本思想：让FA模拟RG的派生。 设G=(V，T，P，S)，且ε?L(G)， 取FA M=( V∪{Z}，T，δ，S，{Z})，Z?V。 * * 3.5.1 FA与右线性文法 对?(a，A)∈T×V {B|A?aB∈P}∪{Z} 如果A?a∈P δ(A，a)= {B|A?aB∈P} 如果A?a?P 用B∈δ(A，a)与产生式A?aB对应 用Z∈δ(A，a)与产生式A?a对应。 * * 3.5.1 FA与右线性文法 （2）证明L(M)=L(G) 对于a1a2…an-1an∈T+， a1a2…an-1an∈L(G) ? S?+ a1a2…an-1an ? S?a1A1 ? a1a2A2 ?… ? a1a2…an-1An-1 ? a1a2…an-1an ? S?a1A1，A1?a2A2，…， An-2?an-1An-1，An-1?an∈P * * 3.5.1 FA与右线性文法 A1∈δ(S，a1)，A2∈δ(A1，a2)，…， An-1∈δ(An-2，an-1)，Z∈δ(An-1，an) ? Z∈δ(S，a1a2…an-1an ) ? a1a2…an-1an∈L(M) 对于 ε，按照定理2-5和定理2-6处理。 * * 3.5.1 FA与右线性文法 例 3-10 构造与所给正则文法等价的FA： G1：E?0A|1B A?1|1C B?0|0C C?0B|1A * * 3.5.1 FA与右线性文法 δ(E，0)={A} 对应E?0A δ(E，1)={B} 对应E?1B δ(A，1)={Z,C} 对应A?1|1C δ(B，0)={Z,C} 对应B?0|0C δ(C，0)={B} 对应C?0B δ(C，1)={A} 对应C?1A * * 3.5.1 FA与右线性文法 * * 3.5.1 FA与右线性文法 推论3-1 FA与正则文法等价。 证明：根据定理3-3和定理3-4即可得到。 * * 3.5.1 FA与左线性文法 按照推导来说，句子a1a2…an-1an中的字符被推导出的先后顺序正好与它们在句子中出现的顺序相反；而按照归约来看，它们被归约成语法变量的顺序则正好与它们在句子中出现的顺序相同：a1，a2，…，an-1，an。可见，归约过程与FA处理句子字符的顺序是一致的，所以可考虑依照“归约”来研究FA的构造。 * * 3.5.1 FA与左线性文法 对于形如A?a的产生式：在推导中，一旦使用了这样的产生式，句型就变成了句子，而且a是该句子的第一个字符；按“归约”理解，对句子的第1个字符，根据形如A?a的产生式进行归约。对应到FA中，FA从开始状态出发，读到句子的第一个字符a，应将它“归约”为A。我们如果考虑用语法变量对应FA的状态，那么，此时我们需要引入一个开始状态，比如说：Z。这样，对应形如A?a的产生式，可以定义A∈δ(Z，a)。 * * 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与左线性文法 定理3-5 左线性文法与FA等价。 * * 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