资源描述：
《03有限自动机new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、形式语言与自动机FormalLanguagesandAutomataTheory第三章有穷自动机教师：康建初、胡春明、赵永望第三章有穷状态自动机一、有穷状态自动机FA定义与表示第一二、确定的有穷自动机DFA次课三、非确定的有穷自动机NFA四、DFA和NFA的等价性五、带空移动的有穷自动机ε-NFA第二六、FA是正则语言的识别器次课七、FA的变形-带输出的FA语言的识别给定一个文法G，定义一个语言L(G)∀?∈?∗,是否有?∈?(?)?(w是语言L的句子吗？)方法1：根据G的定义，寻找一个派生，或归约∗考察??在G中是否成立.有时会出现“回
2、溯”：在一个时候有多个可能的推导规则；判定效率低。一、有穷状态自动机定义与表示识别正则语言的有穷自动机（FA）模型实例：例：??=*???
3、?≥?+⋃*???
4、?≥?+。例：识别aaad有穷状态自动机定义与表示自动机系统的结构及功能特征分析：1、字母表：系统处理的所有字符串由字母表上的字符组成；2、控制器：系统每次从输入字符串读入一个字符，并根据当前状态和读入的字符，转入新的状态；新的状态和当前状态可以相同也可不同；为此，系统具有有穷个状态,并需要维护一个读指针。3、几个特殊状态：一个开始状态；系统从此开始处理句子；一些称之为终止状态
5、或接受状态，系统从开始状态至此状态为止，读入字符构成的字符串是语言的一个句子；系统到达这些状态读入的全部字符串构成系统所能识别的语言。有穷状态自动机定义与表示有穷状态自动机装置的物理模型：有穷状态自动机定义与表示有穷状态自动机装置的组成：1、一个具有一系列方格的输入字符串的带子：方格中存放字符，字符从输入带左端开始存放，输入带右端无穷；2、一个有穷状态控制器FSC：控制一个读头；每读入一个字符，读头右移一格，指向下一个待读入字符。有穷状态控制器FSC的基本工作过程：控制器执行动作由三个节拍组成：⑴读头读入当前指向的字符；⑵根据读入的字符和
6、其自身当前状态，改变有穷状态控制器的状态；⑶读头右移一格指向下一个字符。有穷状态自动机定义与表示定义3.1：一个FA为五元组?=。其中，Q：非空有限的状态集合。?：非空有限输入字符表。?:?×?→?：状态转移函数：对∀?∈?，∀?∈?:??,?=?表示在状态q下读入字符a，M将状态变成p，读头向右移动一个方格，指向输入字符串的下一个字符。qM的开始状态，q∈Q。0：0F：M的终止状态，或接受状态。8有穷状态自动机定义与表示设有限自动机?=,其中，Q={q0,q1,q2,q3}；∑={0
7、,1,2}；δ:Q×∑→Q：函数表示法：状态图表示法：δ(q0,0)=q1δ(q0,1)=q3δ(q0,2)=q3{1,2}δ(q,0)=qδ(q,1)=qδ(q,2)=qq11213130{0,1,2}δ(q2,0)=q1δ(q2,1)=q3δ(q2,2)=q3δ(q3,0)=q3δ(q3,1)=q3δ(q3,2)=q300{1,2}q3q0状态表表示法：012状态说明q0q1q3q3开始状态{1,2}q2q1q2q3q3q2q1q3q3终止状态q3q3q3q3有穷状态自动机定义与表示定义3-2：设FA?=,满足
8、如下条件的有向图称为M的状态转移图：1、q∈Q：q是有向图的一个节点；2、δ(q,a)=p：图中有一条从节点q到节点p的标记为a的弧;3、q∈F：节点q用双层圈标出；4、用标有S的箭头指出M的开始状态。注：状态转移图中可能存在一些并行弧，其从同一节点出发，到达同一节点。一个例子:例3-3.(p.93).构造一个DFA，它接受的语言为*????
9、?∈*?,?+∗+分析：目标是构造一个DFA，识别串x是否有连续的3个0作为结尾.状态0.目前已经读入了0个0，即xxxx1或1状态1.目前已经读入了1个0，即xxxx10或0状态2.目前已经读入了
10、2个0，即xxxx100或00状态3.目前已经读入了3个0，即xxxx1000或00011000S????????11有穷状态自动机定义与表示关于FA的几个基本概念：1、基于字符串的状态转移函数δ’2、FA的瞬时（即时）描述3、FA状态对读入字符串的存储功能4、何谓FA识别一个句子或语言5、FA的等价性有穷状态自动机定义与表示（1）状态转移函数?的推广：??,?→?(?,?)定义FM的目的是为了用来识别语言的句子；因此，有必要将状态转移函数?的定义域从?×?推广到?×?∗。有穷状态自动机定义与表示定义3.1的补充定义：设函数?:?×?∗→
11、?，对于∀?∈?,∀?∈?∗,∀?∈?，有(1)??,?=?读入空串(2)??,??=?(??,?,?)读入非空串有穷状态自动机定义与表示说明1：DFA从状态q出发处理字符串wa的状态转移过程
