第03章 有穷状态自动机-19、20、21节课-2011-10-22.pptVIP

3.4 带空移动的有穷状态自动机 修改条件 接受语言{0n1m2k|n，m，k≥0}的NFA 对NFA进行修改 接受语言{0n1m2k|n，m，k≥0}的NFA是否可以构造成下图所示的“ε-NFA ”？ 定义3-9 带空移动的不确定的有穷状态自动机(non-deterministic finite automaton with ?-moves, ?-NFA) M是一个五元组： M = (Q, ?, ?, q0, F) 其中，Q, ?, q0, F 状态的意义同DFA (定义3-1)。 ? —状态转移函数。 ? : Q? (??{?}) ? 2Q。 定义3-9(续) 非空移动 ?(q，a)∈Q×∑ δ(q，a)= {p1，p2，…，pm} 表示M在状态q读入字符a，可以选择地将状态变成p1、p2、…或者pm ，并将读头向右移动一个带方格而指向输入字符串的下一个字符。 定义3-9(续) 空移动 ?q∈Q δ(q，ε)= {p1，p2，…，pm} 表示M在状态q不读入任何字符，可以选择地将状态变成p1、p2、…或者pm 。 也可以叫做M在状态q做一个空移动(又可以称为ε移动)，并且选择地将状态变成 p1、p2、…或者pm。 扩充? 进一步扩充δ的定义域：Q×∑*?2Q。 对任意的P?Q，w∈∑* 。 对任意的q∈Q，w∈∑*，a∈∑。 扩充?（续） 扩充? （续） 进一步扩展移动函数：2 Q×∑?2Q 。 对任意(P，a)∈2 Q×∑。 扩充? （续） 在ε-NFA中，对任意a∈∑，q∈Q， 比较 M接受(识别)的语言 M接受(识别)的语言 对于?x∈∑*，仅当 定理3-2 ?-NFA与NFA等价。 证明思路： (1) 显然， NFA是?-NFA的特殊形式；即所有的NFA 已经用?-NFA的形式表示； (2) 需要证明对于任意给定的?-NFA ，存在与之等价的NFA 。 定理3-2（续） 设有?-NFA M1 = (Q, ?, ?1, q0, F) (1) 构造与之等价的NFA 取 NFA M2 = (Q, ?, ?2, q0, F2)，其中 对?(q, a) ? Q? ? ，使?2 (q, a) = (q, a) 定理3-2（续） (2) 施归纳于|x|，证明对?x∈∑+ 。 定理3-2（续） 定理3-2（续） (3) 证明, 对?x∈∑+，δ2(q0，x) ∩ F2≠Φ 的充分必要条件是 例3-8 ? 取值 例3-8 ? 练习(见习题) 15. (1) 要求： 画出?-NFA状态转移图； 用表列出NFA状态转移函数； 画出NFA状态转移图。 习题评讲 ?-NFA状态转移图 习题评讲(续) NFA状态转移函数 习题评讲 NFA状态转移图(已化简) 思考 FA的处理过程 文法的推导过程 有没有联系？ 3.5 FA是正则语言的识别器 正则文法的推导过程 与DFA的处理过程 相对应 ??? 3.5.1 FA与右线性文法 DFA M=(Q，∑，δ，q0，F)，处理句子a1a2…an的特性。 ⑴ M按照句子a1a2…an中字符的出现顺序，从开始状态q0开始，依次处理字符 a1、a2、…、an，在这个处理过程中， 每处理一个字符进入一个状态， 最后停止在某个终止状态。 3.5.1 FA与右线性文法 ⑵ 它每次处理且仅处理一个字符： 第i步处理输入字符ai。 ⑶ 使用δ(q，a)=p的状态转移函数的处理， 相当于是在状态q完成对a的处理， 然后由p接下去实现对后续字符的处理。 ⑷ 当δ(q，a)=p∈F，且a是输入串的最后 一个字符时，M完成对此输入串的处理。 3.5.1 FA与右线性文法 A0? a1A1 对应产生式A0? a1A1 ? a1a2A2 对应产生式A1? a2A2 … ? a1a2…an-1An-1 对应产生式An-2? an-1An-1 ? a1a2…an-1an 对应产生式An-1? an 3.5.1 FA与右线性文法 q0 a1a2…an-1an ├a1q1 a2…an-1an 对应δ(q0，a1)=q1 ├a1a2q2…an-1an 对应δ(q1，a2)=q2 …… ├a1a2…an-1qn-1an 对应δ(qn-2，an-1)=qn-1 ├a1a2…an-1anqn 对应δ(qn-1，an)=qn 3.5.1 FA与右线性文法 其中qn为M的终止状态。 考虑根据a1、a2、…、an，