形式语言自动机――有限自动机课件.ppt

《形式语言自动机――有限自动机课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章有限自动机与右线性文法本章主要内容确定有限自动机非确定有限自动机确定与非确定有限自动机的等价性带ε转移的有限自动机右线性文法和有限自动机的等价性，右线性文法的性质(泵浦定理)使用归纳法进行证明的方法。1CollegeofComputerScience&Technology,BUPT第一节有限自动机一、有限状态系统的概念状态:状态是可以将事物区分开的一种标识。具有离散状态的系统:如数字电路(0,1),十字路口的红绿灯。离散状态系统的状态数是有限的.具有连续状态的系统:比如水库的水位,室内温度等可以连续变化,即有无穷个状态.有限状态系统必然是离散

2、状态系统（而且状态数有限）,因为只有有限个状态.2CollegeofComputerScience&Technology,BUPT第一节有限自动机实例一个人带着一头狼，一头羊，以及一棵青菜，处于河的左岸。有一条小船,每次只能携带人和其余的三者之一。人和他的伴随品都希望渡到河的右岸，而每摆渡一次，人仅能带其中之一。然而如果人留下狼和羊不论在左岸还是在右岸，狼肯定会吃掉羊。类似地，如果单独留下羊和菜，羊也肯定会吃掉菜。如何才能既渡过河而羊和菜又不被吃掉呢?3CollegeofComputerScience&Technology,BUPTMG－WC（处于

3、左岸的子集－处于右岸的子集）将过河问题模型化：人(M)狼(W)羊(G)菜(C)4CollegeofComputerScience&Technology,BUPT二、有限自动机的概念有限自动机的概念具有离散输入输出系统的一种数学模型(可以没有输出，比较特殊的也可以没有输入).有限的状态状态+输入状态转移每次转换的后继状态都唯一DFA每次转换的后继状态不唯一NFA5CollegeofComputerScience&Technology,BUPTFA的模型FA可以理解成一个控制器,它读一条输入带上的字符。101101有限控制器(1)控制器包括有限状

4、态;(2)从左到右依次读取字符;(3)状态+激励状态迁移(根据当前所处状态和输入字符进行状态转移)6CollegeofComputerScience&Technology,BUPT有限状态集有限输入符号集转移函数一个开始状态一个终态集合有限自动机的五要素q0q1q2q37CollegeofComputerScience&Technology,BUPT三、DFA的形式定义定义:DFA是一个五元组M=(Q,T,δ,q0,F)Q:有限的状态集合T:有限的输入字母表δ:转换函数(状态转移集合):Q×TQq0:初始状态，q0QF:终止状态集,FQ表示

5、方法：8CollegeofComputerScience&Technology,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}q0q1q2q39CollegeofComputerScience&Technology,BUPT转移表表示的DFAq0q1q2q301q2q1q3q0q0q3q1q2Q={q0,q1,q2,q3}T={0,1

6、}(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}10CollegeofComputerScience&Technology,BUPT四、扩展转移函数适合于输入字符串δ’函数：接收一个字符串的状态转移函数。:QT*Q对任何qQ，定义：1.(q,)=q2.若ω是一个字符串,a是一个字符定义:δ’(q,ωa)=δ(δ’(q,ω),a)对于DFA:δ’(q,a)=δ(δ‘(q,),a)=δ(q,a

7、)，即对于单个字符时δ和δ'是相等的。为了方便，以后在不引起混淆时用δ代替δ'11CollegeofComputerScience&Technology,BUPT扩展转移函数适合于输入字符串q0q1q2q301q2q1q3q0q0q3q1q2举例(q0,)=q0(q0,0)=(q0,0)=q2(q0,00)=(q2,0)=q0(q0,001)=(q0,1)=q1(q0,0010)=(q1,0)=q3q0q1q2q312CollegeofComputerScience&Technology,BUPTDFA接受的语言被

8、DFA接收的字符串:输入结束后使DFA的状态到达终止状态。否则该字符串不能被DFA接收.DFA接收的语言:被DFA接收的字