计算理论课件第二章.ppt

《计算理论课件第二章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章有限自动机和正规文法2.1确定的有限自动机(DFA)(DeterminateFiniteAutomaton)有限自动机是研究自动系统的一种数学模型，它出现于本世纪四十年代。1943年由McCulloch与Pitts建立了模拟神经网络的自动机,1956年由Moore建立了描述计算机的时序机的概念。以后自动机的理论日趋发展，并且与计算机的信息处理密切结合，它不仅用于研究计算机的结构，还用于研究形式语言——语言的识别。在这里主要是从识别语言这方面来研究自动机。一.有限自动机(FA)的结构有限自动机由三部分构成：1.输入带输入带可以任意长，带上有若干单元，每个单元

2、内有输入符号。输入带上存放的是被有限自动机识别的符号串。如图所示，输入带上的符号串为：a1a2a3…an。2.读头读头是将输入带上的符号读到有限控制器中，每次读一个单元的符号。有限控制器a1a2a3…an输入带读头3.有限控制器有限控制器是有限自动机的核心。有限自动机有多个状态，有一个开始状态，还有若干个终止状态。自动机每读带上一个符号,状态可能发生变化，然后读头右移一个单元。自动机如何从开始状态出发，识别完带上的整个符号串后，要进入某个终止状态，这个过程就是由有限控制器控制的。二.确定的有限自动机(DFA)的形式描述定义：确定的有限自动机M写成有序五元组，记作

3、M=(K,∑,δ,q0,F)其中，K——有限自动机的状态的有限集合。∑——输入带上的有穷字母表。δ——状态转移函数,是K×∑→K的映射。例如，δ(q,a)=p(其中q,p∈K,a∈∑),表示在q状态下，读a后，状态改为p,然后，将读头右移一个单元。q0——开始状态q0∈KF——终止状态集合，FK三.确定的有限自动机的表示方法【例2-1.1】给定确定的有限自动机M=(K,∑,δ,q0,F)K={q0,q1,q2,q3},∑={0,1},F={q0}δ:δ(q0,0)=q2δ(q0,1)=q1δ(q1,0)=q3δ(q1,1)=q0δ(q2,0)=q0δ(q2,1

4、)=q3δ(q3,0)=q1δ(q3,1)=q2状态转移函数δ也可以用函数表表示，如上表所示。01q0q2q1q1q3q0q2q0q3q3q1q2aqδ(q,a)=q(c)qqF(d)q0开始状态q0(a)qpδ(q,a)=p(b)a有限自动机还可以用图表示。方法如下：四．状态转移函数δ定义的扩充原δ：K×∑→K的映射。1100q0q1q2q3110001q0q2q1q1q3q0q2q0q3q3q1q2(q,ε)=qM的状态转移图:为描述有限自动机M接收的语言，将δ函数扩充成：：K×∑*→K的映射。对于任何x∈∑*，如果一般地表示：(q,x)=p,表示在状态q

5、下，读符号串x后，到状态p。(q,xa)=δ((q,x),a)其中x∈∑*，a∈∑例如上例中(q0,010)=δ((q0,01),0)=δ(δ((q0,0),1),0)＝δ(δ(q2,1),0)=δ(q3,0)=q1。＝δ(δ(δ((q0,ε),0),1),0)=δ(δ(δ(q0,0),1),0)但此时的δ一定理解成。(q0,010)=q1也可以写成δ(q0,010)=q1。造成混淆，所以起见，符号δ与可以不作区分地使用，这样做也不会可见在确定的有限自动机中，是由δ定义的,为了简单五．确定的有限自动机M接收的语言T(M)给定确定的有限自动机M=(K,∑,δ,q0

6、,F)，M接收的语言T(M)为：T(M)={w

7、w∈∑*且δ(q0,w)=p其中p∈F}例2-1.1中，T(M)=?1100q0q1q2q31100T(M)={w

8、w∈{0,1}*且w中有偶数个0或者偶数个1}。作业题1．设计一个有限自动机(FA)M，使得T(M)中的每个句子w同时满足下面三个条件：1)w∈{a,b,}*；2)

9、w

10、是3的整数倍；3)w以a开头，以b结尾。2．设计二个FAM1和M2，分别满足T(M1)={02i∣i是自然数}T(M2)={02i+1∣i=0,1,2,3,4,…}2.2不确定的有限自动机（NFA）(Non-deterministic

11、FiniteAutomaton)DFA是在每个状态下，读一个符号后的下一个状态是唯一确定的，下面讨论的有限自动机是在某个状态下，读一个符号后的下一个状态可能不是唯一确定的，这就是不确定的有限自动机。一.不确定的有限自动机（NFA）的形式定义定义：不确定的有限自动机M，用一个有序五元组表示：M=(K,∑,δ,q0,F)其中，K、∑、q0、F的含义同DFA。δ—状态转移函数,是K×∑→2K的映射。例.δ(q,a)={p,s}(其中q∈K,{p,s}∈2Ka∈∑)【例2-2.1】.给定NFAM，M=(K,∑,δ,q0,F)其中，K={q0,q1,q2,q3,q4}∑=

12、{0,1}F={q2,q