形式语言与自动机-2015-第03讲-有穷自动机(1)

《形式语言与自动机-2015-第03讲-有穷自动机(1)》由会员分享，可在线阅读，更多相关《形式语言与自动机-2015-第03讲-有穷自动机(1)（59页珍藏版）》请在文档大全上搜索。

1、形式语言与自动机形式语言与自动机Formal Languages and Automata Theory教师：康建初、胡春明、教师：康建初、胡春明、赵永望赵永望http:/ 有穷自动机有穷自动机第三章第三章 有穷状态自动机有穷状态自动机一、有穷状态自动机一、有穷状态自动机 FA FA 定义与表示定义与表示二、确定的有穷自动机二、确定的有穷自动机 DFADFA三、非确定的有穷自动机三、非确定的有穷自动机 NFANFA四、四、DFA DFA 和和 NFA NFA 的等价性的等价性五、带空移动的有穷自动机五、带空移动的有穷自动机- NFA- NFA六、六、FA FA 是正则语言的识别器是正则语言的识

2、别器 七、七、FA FA 的变形的变形 - - 带输出的带输出的 FAFA第第一一次课次课第二第二次课次课语言的识别语言的识别方法方法1：根据：根据G的定义，寻找一个派生，或归约的定义，寻找一个派生，或归约一、有穷状态自动机定义与表示一、有穷状态自动机定义与表示自动机系统的自动机系统的结构及功能特征分析结构及功能特征分析： 1 1、字母表：系统处理的所有字符串由字母表上的字符组成；、字母表：系统处理的所有字符串由字母表上的字符组成；2 2、控制器：系统每次从输入字符串读入一个字符，并根据当前状态、控制器：系统每次从输入字符串读入一个字符，并根据当前状态和读入的字符，转入新的状态；新的状态和当前

3、状态可以相同也可不和读入的字符，转入新的状态；新的状态和当前状态可以相同也可不同；为此，系统具有有穷个状态同；为此，系统具有有穷个状态, ,并需要维护一个读指针。并需要维护一个读指针。3 3、几个特殊状态：、几个特殊状态： 一个开始状态；系统从此开始处理句子；一个开始状态；系统从此开始处理句子； 一些称之为终止状态或接受状态，系统从开始状态至此状态为一些称之为终止状态或接受状态，系统从开始状态至此状态为止，读入字符构成的字符串是语言的一个句子；系统到达这些止，读入字符构成的字符串是语言的一个句子；系统到达这些状态读入的全部字符串构成系统所能识别的语言。状态读入的全部字符串构成系统所能识别的语言

4、。有穷状态自动机定义与表示有穷状态自动机定义与表示有穷状态自动机装置的物理模型：有穷状态自动机装置的物理模型： 有穷状态自动机定义与表示有穷状态自动机定义与表示有穷状态自动机装置的组成：有穷状态自动机装置的组成： 1、一个具有一系列方格的输入字符串的带子：方格中存放字、一个具有一系列方格的输入字符串的带子：方格中存放字符，字符从输入带左端开始存放，符，字符从输入带左端开始存放，输入带右端无穷输入带右端无穷； 2、一个有穷状态控制器、一个有穷状态控制器 FSC：控制一个读头；每读入一个字：控制一个读头；每读入一个字符，读头右移一格，指向下一个待读入字符。符，读头右移一格，指向下一个待读入字符。有

5、穷状态控制器有穷状态控制器 FSC 的基本工作过程：的基本工作过程： 控制器执行动作由三个节拍组成：控制器执行动作由三个节拍组成： 读头读入当前指向的字读头读入当前指向的字符；符； 根据读入的字符和其自身当前状态，改变有穷状态控制根据读入的字符和其自身当前状态，改变有穷状态控制器的状态；器的状态； 读头右移一格指向下一个字符。读头右移一格指向下一个字符。有穷状态自动机定义与表示有穷状态自动机定义与表示8有穷状态自动机定义有穷状态自动机定义与表示与表示(q0, 0)=q1 (q0, 1) = q3 (q0, 2) = q3 (q1, 0)=q2 (q1, 1) = q3 (q1, 2) = q3

6、 (q2, 0)=q1 (q2, 1) = q3 (q2, 2) = q3 (q3, 0)=q3 (q3, 1) = q3 (q3, 2) = q3 状态表表示法：状态表表示法：状态图表示法：状态图表示法：q0q3q1q2 1, 2 1, 2 1,2 00 0,1,2 0012状态说明状态说明q0q1q3q3 开始状态开始状态q1q2q3q3q2q1q3q3终止状态终止状态q3q3q3q3有穷状态自动机有穷状态自动机定义与定义与表示表示函数表示法：函数表示法：有穷状态自动机有穷状态自动机定义与表示定义与表示注：状态转移图中可能存在一些并行弧，其从同一节点出发，到达同注：状态转移图中可能存在一些

7、并行弧，其从同一节点出发，到达同一节点。一节点。11一个例子一个例子:分析：目标是构造一个分析：目标是构造一个DFA，识别串，识别串x是是否有连续的否有连续的3个个0作为结尾作为结尾.状态状态0. 目目前已经读入了前已经读入了0个个0，即，即 xxxx1或或1状态状态1. 目目前已经读入了前已经读入了1个个0，即，即 xxxx10或或0状态状态2. 目目前已经读入了前已经读入了2个个0，即，即 xxxx100或或00状态状态3. 目目前已经读入了前已经读入了3个个0，即，即 xxxx1000或或0000001S1有穷状态自动机定义有穷状态自动机定义与表示与表示关于关于 FA 的几个基本概念：的

8、几个基本概念：1、基于字符串的状态转移函数、基于字符串的状态转移函数2、FA 的瞬时（即时）描述的瞬时（即时）描述3、FA 状态对读入字符串的存储功能状态对读入字符串的存储功能4、何谓、何谓 FA 识别一个句子或语言识别一个句子或语言5、FA 的等价性的等价性有穷状态自动机定义有穷状态自动机定义与表示（与表示（1）定义定义3.1的补充定义：的补充定义：有穷状态自动机定义有穷状态自动机定义与表示与表示读入空串读入空串读入非空串读入非空串对于任意的对于任意的 q Q, w , a ，有：，有：( q, wa ) = ( ( q, w ), a ) =( ( q, a1 a2 a3 an），）， a

9、 ) = ( ( ( q, a1 ), a2 ), an ), a ) 说明说明 1 1：DFA DFA 从状态从状态 q q 出发处理字符串出发处理字符串 wa 的状态转移过程：的状态转移过程：有穷状态自动机定义有穷状态自动机定义与表示与表示说明说明 2：由于由于 Q是是 Q* 的真子集；对于任意输入字符的真子集；对于任意输入字符 a，有，有 ( q, a ) = ( q, a ) 是单位元素是单位元素 = ( ( q, ), a ) 由补充定义第由补充定义第 2 条条 =( q, a ) 由补充定义第由补充定义第 1 条条有穷状态自动机定义有穷状态自动机定义与表示与表示可见，状态转移函数可

10、见，状态转移函数 可以涵盖描述可以涵盖描述 ，因此，不必区分的，因此，不必区分的使用使用和和 ，通常一般性地用，通常一般性地用代替代替 。定义定义 3.3：设设 FA M = ( Q, , , q0, F )，x, y*，( q0, x ) = q , x q y 称为称为 M 的一个瞬时描述（的一个瞬时描述（ID），）， 表示：表示：xy 是是 M 正在处理的一个字符串，其子串正在处理的一个字符串，其子串 x 引导引导 M 从从 q0 启动，到达状态启动，到达状态 q, M 的读头当前指向子串的读头当前指向子串 y 的首的首字符。字符。有穷状态自动机定义有穷状态自动机定义与表示（与表示（2）

11、如果如果 xqay 是是 M 一个瞬时描述一个瞬时描述, 且且 （ q, a ）= p ，则有：，则有： xqay xapy 表示表示 M 在状态在状态 q 时已处理完字符串时已处理完字符串 x；当前读入的字符为；当前读入的字符为 a且转入状态且转入状态 p, 然后将读头向右移动一格，指向字符串然后将读头向右移动一格，指向字符串 y 的首字符。的首字符。MFA M 的瞬时移动描述：的瞬时移动描述：有穷状态自动机定义有穷状态自动机定义与表示与表示FA M 的瞬时移动序列描述的瞬时移动序列描述： ：M 从已识别的字符串从已识别的字符串 出发，经过出发，经过 n 次移动，次移动，识别的字符串变为识别