北京邮电大学形式语言自动机课件.ppt

12024/9/5CollegeofComputerScienceTechnology,BUPT第三章有限自动机与右线性文法本章主要内容确定有限自动机非确定有限自动机确定与非确定有限自动机的等价性右线性文法和有限自动机的等价性，右线性文法的性质(泵浦定理)使用归纳法进行证明的方法。

22024/9/5CollegeofComputerScienceTechnology,BUPT第一节有限自动机一、有限状态系统的概念状态:状态是可以将事物区分开的一种标识。具有离散状态的系统:如数字电路(0,1),十字路口的红绿灯。离散状态系统的状态数是有限的.具有连续状态的系统:比方水库的水位,室内温度等可以连续变化,即有无穷个状态.有限状态系统必然是离散状态系统〔而且状态数有限〕,因为只有有限个状态.

32024/9/5CollegeofComputerScienceTechnology,BUPT实例 一个人带着一头狼，一头羊，以及一棵青菜，处于河的左岸。有一条小船,每次只能携带人和其余的三者之一。人和他的伴随品都希望渡到河的右岸，而每摆渡一次，人仅能带其中之一。然而如果人留下狼和羊不管在左岸还是在右岸，狼肯定会吃掉羊。类似地，如果单独留下羊和菜，羊也肯定会吃掉菜。如何才能既渡过河而羊和菜又不被吃掉呢?

42024/9/5CollegeofComputerScienceTechnology,BUPTMG－WC〔处于左岸的子集－处于右岸的子集〕将过河问题模型化：人(M)狼(W)羊(G)菜(C)

52024/9/5CollegeofComputerScienceTechnology,BUPT二、有限自动机的概念有限自动机的概念具有离散输入输出系统的一种数学模型 (可以没有输出，比较特殊的也可以没有输入).有限的状态状态+输入?状态转移每次转换的后继状态都唯一?DFA每次转换的后继状态不唯一?NFA

62024/9/5CollegeofComputerScienceTechnology,BUPTFA的模型 FA可以理解成一个控制器,它读一条输入带上的字符。101101有限控制器(1)控制器包括有限状态;(2)从左到右依次读取字符;(3)状态+鼓励?状态迁移 (根据当前所处状态和输入字符进行状态转移)

72024/9/5CollegeofComputerScienceTechnology,BUPT有限状态集有限输入符号集转移函数一个开始状态一个终态集合有限自动机的五要素q0q1q2q3

82024/9/5CollegeofComputerScienceTechnology,BUPT三、DFA的形式定义定义:DFA是一个五元组M=(Q,T,δ,q0,F)Q:有限的状态集合T:有限的输入字母表δ:转换函数(状态转移集合):Q×T?Qq0:初始状态，q0?QF:终止状态集,F?Q

92024/9/5CollegeofComputerScienceTechnology,BUPT转移图表示的DFAQ={q0,q1,q2,q3}T={0,1}?(q0,0)=q2,?(q0,1)=q1?(q1,0)=q3,?(q1,1)=q0?(q2,0)=q0,?(q2,1)=q3?(q3,0)=q1,?(q3,1)=q2q0F={q0,q3}q0q1q2q3

102024/9/5CollegeofComputerScienceTechnology,BUPT转移表表示的DFA?q0q1q2?q301q2q1q3q0q0q3q1q2Q={q0,q1,q2,q3}T={0,1}?(q0,0)=q2,?(q0,1)=q1?(q1,0)=q3,?(q1,1)=q0?(q2,0)=q0,?(q2,1)=q3?(q3,0)=q1,?(q3,1)=q2q0F={q0,q3}

112024/9/5CollegeofComputerScienceTechnology,BUPT四、扩展转移函数适合于输入字符串δ’函数：接收一个字符串的状态转移函数。 ??:Q?T*?Q对任何q?Q，定义：1.?