形式语言与自动机有穷自动机

1形式语言与自动机第三章有穷自动机南京航空航天大学计算机科学与技术学院胡军[e-mail]2020年1月1日星期三南京航空航天大学计算机学院胡军2第三章有穷自动机1.1非形式化描述1.2有穷自动机的基本定义1.3非确定的有穷自动机1.4具有ε转移的有穷自动机1.5有穷自动机的应用1.6具有输出的有穷自动机（*)2020年1月1日星期三南京航空航天大学计算机学院胡军31.1有穷状态系统指针式钟表共有12*60*60个状态小时×分钟×秒围棋共有3361个状态每一个格子：（空，黑，白）；格子数量：19行×19列某些电子产品中的开关电路，具有n个门的开关网络有2n种状态“网上购物”系统（示例：）2020年1月1日星期三南京航空航天大学计算机学院胡军42007年图灵奖模型检验（modelchecking）:基于自动机理论的形式化方法(formalmethods)E.ClarkEmersonSifakis2020年1月1日星期三南京航空航天大学计算机学院胡军51.2有穷自动机的基本定义定义3.1一个有穷自动机(FiniteAutomata)简称FA，是一个五元组：M=(Q,∑,δ,q0,F)，其中（1）Q是有穷状态集；（States）（2）∑是有穷的输入字母表（Alphabet）（3）δ是转移函数，它将Q×∑→Q(全映射)；（Transistonfunction）（4）q0∈Q，是初始状态；（Initialstate）（5）FQ，是终结状态集。（Acceptingstates）(终止状态，接受状态)上述定义的另一个说法：确定型的有穷自动机(DeterministicFiniteAutomata：DFA)2020年1月1日星期三南京航空航天大学计算机学院胡军6DFA例子q0q1q21000,11字母表：S={0,1}状态集：Q={q0,q1,q2}初始状态：q0终结状态:F={q0,q1}状态集输入01q0q1q2q0q1q2q2q2q1转换函数表d:**→问题：1.接受什么特征的字符串？2.状态q2起什么作用？2020年1月1日星期三南京航空航天大学计算机学院胡军7这两个DFA所接受的字符串集合分别是什么？DFA例子q0q1baabS={a,b}q0q1q2q3q4aaaaabbbbbS={a,b}2020年1月1日星期三南京航空航天大学计算机学院胡军8设计一个DFA(字母表为{0,1}),接受如下字符串：设计一个DFA(字母表为{0,1}),接受如下特征的字符串：最多有三个1.q0q1011q20q31q4+0,1010DFA例子L={010,1}qeq0q1q01q010qdie0,10100,11010,12020年1月1日星期三南京航空航天大学计算机学院胡军9设计一个DFA(字母表为{0,1}),接受所有结尾是01的字符串。提示：DFA得记住读入字符串的最后两位。DFA例子qe01q0q1q00q10q01q11010100111002020年1月1日星期三南京航空航天大学计算机学院胡军10设计一个DFA(字母表为{0,1}),接受所有结尾是101的字符串。DFA例子2020年1月1日星期三南京航空航天大学计算机学院胡军11例3.1给出一个有穷自动机Ｍ=({q0,q1,q2,q3},{0,1},δ,q0,{q0})其中：转移函数δ具体定义如下：δ(q0,1)=q1δ(q0,0)=q2δ(q1,1)=q0δ(q1,0)=q3δ(q2,1)=q3δ(q2,0)=q0δ(q3,1)=q2δ(q3,0)=q1→*DFA例子2020年1月1日星期三南京航空航天大学计算机学院胡军12有穷自动机的扩充定义定义3.2对于有穷自动机M=(Q，∑，δ，q0，F)，它的扩充转移函数,是从Q×∑*到Q的映射，其具体定义如下：（1）(q,ε)=q；（2）(q,wa)=δ((q,w),a)。其中q∈Q，w∈∑*，a∈∑。例如，对于例3.1中的有穷自动机，就有：(q0,010)=δ((q0,01),0)=δ(δ((q0,0),1),0)=δ(δ(δ((q0,ε),0),1),0)=δ(δ(δ(q0,0),1),0)=δ(δ(q2,1),0)=δ(q3,0)=q1。dˆdˆdˆdˆdˆdˆdˆdˆ2020年1月1日星期三南京航空航天大学计算机学院胡军13有穷自动机的基本定义从δ到的扩充是很自然的，δ就是的特例（当|x|=1时）。今后在提到FA的转移函数时，不再强调这种写法，一律用δ表示，即δ的第二个变元既可以是单个字符也可以是一个字符串。dˆdˆdˆ2020年1月1日星期三南京航空航天大学计算机学院胡军14有穷自动机模型开始时，“读头”指向带上的第一个输入符号，控制器中放的是FA的初始状态。然后，依据转移函数δ做动作：若控制器中的当前状态是q，且“读头”指向带上符号为a，则控制器中状态将变成p=δ(q,a)，且“读头”向右移指向带上下一个符号，如此可以继续进行下去。(注意：读头不能回头，只能一直向右移动)→*2020年1月1日星期三南京航空航天大学计算机学院胡军15有穷自动机的模型定义3.3给出FA：M=(Q,∑,δ,q0,F)，若δ(q0,x)=p∈F(x∈∑*)，则称字符串x被M接受。进一步地，被M接受的全部字符串构成的集合，称为被有穷自动机M接受的语言，并记为L(M)。用集合描述法就是L(M)={x∣δ(q0,x)∈F}。FA所能接受的只是∑*的一部分子集，有很多∑*的子集是任何FA都不能接受的。2020年1月1日星期三南京航空航天大学计算机学院胡军16从给定集合构造接受该集合的FA例3.3：设计一个接受能被5整除的二进制数的FAM用qs表示初始状态，用q0、q1、q2、q3、q4分别表示二进制数被5整除时余0（即能被5整除，所以它是终结状态。）、余1、余2、余3、余4的状态。2020年1月1日星期三南京航空航天大学计算机学院胡军17一个FA(字母表为{0,1}),接受所有结尾是101的字符串。能否给FA增加猜测选择的能力？假设我们具有猜测何时输入串还剩下三个字符的能力。1.3非确定的有穷自动机(NFA)qdie101还剩三个字符0102020年1月1日星期三南京航空航天大学计算机学院胡军18NFA每个状态对同样的一个输入字符，可能有0,1,或者多条转换发生（猜测）.1010,1q0q1q2q32020年1月1日星期三南京航空航天大学计算机学院胡军19NFA：可以进行猜测选择1010,1q0q1q2q3状态q0有两个标记为1的转换；读入1,NFA可以选择停留在q0，或者继续往前到状态q12020年1月1日星期三南京航空航天大学计算机学院胡军20NFA：可以进行猜测选择1010,1q0q1q2q3状态q1对于输入1没有相应的转换；q1上读入1时,NFA就运行不下去了(die);而读入0时候,NFA可以继续到状态q2；状态q2类似的行为。2020年1月1日星期三南京航空航天大学计算机学院胡军211010,1q0q1q2q3q3没有任何转换出来；q3上如果读入0,1,NFA也运行进入死状态。NFA：可以进行猜测选择2020年1月1日星期三南京航空航天大学计算机学院胡军22NFA：猜测的能力1010,1q0q1q2q3猜测是否已经到了最后三位字符的位置了？如果是，则猜测最后三位字符应该是与101相匹配判断是否到达输入字符串的最末端NFA的运行过程中某个时刻是会同时处于多个状态中，只要输入串x结束时NFA所处的多个状态中至少有一个是接受状态，就判断NFA接受x。2020年1月1日星期三南京航空航天大学计算机学院胡军23NFA的形式化定义定义3.4一个非确定的有穷自动机(NondeterministicFiniteAutomata)简记为NFA，是一个五元组M=(Q,∑,δ,q0,F)其中Q、∑、q0和F与确定的有穷自动机的含意相同，只是转移函数δ的定义不同，它是从Q×∑→2Q（Q的幂集）上的映射。在FA中，δ的一般形式是δ(q,a)=p(q,p∈Q)，而在NFA中，δ的一般形式是δ(q,a)={p1,p2,…,pk}(pi∈Q,i=1,2,…k)，或δ(q,a)=φ（空集）。在NFA中转移函数δ的取值是一个状态集，即使只有一个状态p，也要写成集合形式{p}。2020年1月1日星期三南京航空航天大学计算机学院胡军24NFA的形式化定义定义3.5对于NFAM=(Q,∑,δ,q0,F)，它的扩充转移函数是从Q×∑*→2Q的映射，具体定义如下：(1)(q,ε)={q},(2)(q,wa)={p|p∈δ(r,a),r∈(q,w)}。对于例3.4中的NFA，(q0,01001)的求值过程如下图：dˆdˆdˆdˆ2020年1月1日星期三南京航空航天大学计算机学院胡军25NFA接受的语言定义3.7给出NFAM=(Q,∑,δ,q0,F)，若δ(q0,x)∩F非空（x∈∑*），则称字符串x被M接受。被NFAM接受的全体字符串称为M接受的语言，记作L(M)。也就是L(M)={x∣x∈∑*,且δ(q0,x)∩F非空}。2020年1月1日星期三南京航空航天大学计算机学院胡军26NFA与DFA的等价NFA能识别（接受）DFA所识别（接受）的所有语言。（为什么？）反过来成立吗？任一个NFA都能转换成一个DFA，二者所识别的语言是相等的。YES2020年1月1日星期三南京航空航天大学计算机学院胡军27NFA→DFA:直观的理解100,1q0q1q2NFA:DFA:1q0q0orq11q0orq210002020年1月1日星期三南京航空航天大学计算机学院胡军28NFA→DFA:子集构造法(subsetconstruction)100,1q0q1q2NFA:DFA:{q0,q1}{q0,q2}{q0,q1,q2}{q1,q2}{q0}{q1}{q2}NFA中的任一个状态子集都是所构造的DFA的一个状态2020年1月1日星期三南京航空航天大学计算机学院胡军29NFA→DFA:状态之间的转换100,1q0q1q2NFA:DFA:{q0,q1}{q0,q2}{q0,q1,q2}{q1,q2}{q0}{q1}{q2}0101010101010,12020年1月1日星期三南京航空航天大学计算机学院胡军30NFA→DFA:确定DFA接受状态100,1q0q1q2NFA:DFA:{q0,q1}{q0,q2}{q0,q1,q2}{q1,q2}{q0}{q1}{q2}0101010101010,1DFA中包含NFA接受状态的子集状态设为accepting2020年1月1日星期三南京航空航天大学计算机学院胡军31NFA→DFA:消除无用的状态100,1q0q1q2NFA:DFA:{q0,q1}{q0,q2}{q0}010101{q0,q1,q2}01{q1,q2}{q1}{q2}01010,1将DFA中不可达的状态消除掉。2020年1月1日星期三南京航空航天大学计算机学院胡军32子集构造法的一般步骤NFADFA状态q0,q1,…,qnq0},{q1},{q0,q1},…,{q0,…,qn}每个状态都是NFA的一个子集。初始状态q0q0}转换dd’({qi1,…,qik},a)=d(qi1,a)∪…∪d(qik,a)接受状态FQF’={S:S包含F中至少一个状态}2020年1月1日星期三南京航空航天大学计算机学院胡军33NFA-DFA等价性的形式化证明定理3.1设L是被一个非确定的有穷自动机接受的语言，则存在一个确定的有穷自动机也接受这个语言L。证明设M=(Q,∑,δ,q0,F)是一个接受L的NFA，现在构造一个DFAM´=(Q´,∑,δ´,q0´,F´)，其中：①Q´=2Q,即Q的每一个子集作为Q´的一个状态，若子集为{q1,q2,…,qk}，则Q´中状态记为[q1,q2,…,qk]；②q0´={q0}；③F´2Q:F´的每个元素至少包含F中的一个状态；④δ´的定义为：δ