形式语言自动机——有限自动机与右线性文法(四).ppt

fall 2001 第五讲 3.9 (part 2) 右线性语言的封闭性 3.10 双向和有输出的有限自动机 双向有限自动机 (2DFA) 定义: 读入一个字符之后，读头既可以左移一格，也可以右移一格，或者不移动的有限自动机， 为双向有限自动机. 确定的双向有限自动机: 每读入一字符，必须向左或右移动，不考虑不移动的情况. 2DFA的形式定义 2DFA M＝(Q ，T ，δ， q0， F) δ是从Q×T→Q×{L，R}的映射. 即 δ(q，a)=(p，R) 或 δ(q，a)=(p，L) （在状态q， 读入a， 进入状态p，读头向右(向左)移一格） 用格局描述: 设有ω1qω2 ω1 --- 已输入串 q --- 当前状态 ω2 --- 待输入串 δ(q，am+1)=(p，R)的格局表示: a1 a2…am q am+1…an┣ a1 a2…am+1 p am+2…an δ(q，am+1)=(p，L)的格局表示: a1 a2…am q am+1…an┣ a1 a2…am-1 p am am+1…an 2DFA 2DFA接受的字符串集合是: L(M)={ω| q０ω┣*ωq，q?F} 例: 书P113 例1. 其状态图为 有输出的有限自动机 有输出的有限自动机是有限自动机的一个类型.这类自动机在有字符输入时，不仅存在状态转换，同时引起字符输出. 根据输入字符，自动机状态，输出字符三者之间关系，可有两类有输出的自动机: 米兰机(Mealy): 输出字符与输入字符及状态有关. 摩尔机(Moore): 输出字符仅与状态有关. 最大优点: 节省状态! 米兰机 米兰机形式定义: M＝(Q ，T ，R，δ， g ， q0) 其中 Q 有限状态集合 T 有限输入字母表 R 有限输出字母表 δ: Q×T→Q 转换函数 g : Q×T→R 输出函数 q0: 初始状态 q0?Q δ和g函数共同描述了米兰机的工作状况. 米兰机 米兰机图形表示: 米兰机 课堂练习 课堂练习 课堂练习 摩尔机 摩尔机的输出只与到达的状态有关 形式定义: M＝(Q ，T ，R，δ， g ， q0) g : Q ? R δ: Q ? T ? Q 图形表示: 摩尔机 课堂练习 米兰机和摩尔机的变换 米兰机和摩尔机的变换 *College of Computer Science Technology, BUPT 右线性语言的封闭性 　上节从文法产生的角度证明了右线性语言及其并，积，闭包是正则集；本节用有限自动机接受的语言来证明。 (书P103~) 设Ｌ１和Ｌ２是右线性语言，证明Ｌ１∪Ｌ２为右线性语言  构造NFA M＝(Q ，T ，δ，q0，F) Q＝Q1∪Q２∪｛q0｝ 　 q0是新的起始状态 Ｆ１∪Ｆ２　当ε?Ｌ１，ε?Ｌ２ Ｆ１∪Ｆ２∪｛q０｝ 否则 F = M形如: 右线性语言的封闭性 设Ｌ１和Ｌ２是右线性语言，证明Ｌ１Ｌ２为右线性语言 (书P104~)  构造NFA M＝(Q ，T ，δ， q0， F), 其中Q=Q１∪Q２ q0 =q1 Ｆ２ 当q2?F2 Ｆ１∪Ｆ２ 当q2∈F2 F = M形如: 右线性语言的封闭性 设Ｌ１是右线性语言，证明L１*是右线性语言(书P106~)  构造NFA M＝(Q ，T ，δ，q0，F), Q = Q1∪｛q０｝ q０是新的起始状态, F=Ｆ1∪｛q０｝ L１* 形如 右线性语言的封闭性 设Ｌ１是右线性语言，证明 L１ 是右线性语言 证明：构造接受Ｌ1的M＝(Q ，T ，δ， q0， F) 其中Q = Q1∪｛γ｝ γ是一个新状态 T?T1 q0 =q1 Ｆ＝(Q1－Ｆ1) ∪｛γ｝ (即将Ｍ1的终止状态变为M的非终止状态) δ定义为: 当a∈T1 ，则δ(q，a)= δ1(q，a) — 保留原有函数 当a∈T－T1，则δ(q，a)=γ — 遇到原来没有的字符全转至γ. 对任意a∈T， δ(γ，a)＝γ  右线性语言的封闭性 例: (书P108)