资源描述：
《形式语言与自动机_有穷自动机》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1形式语言与自动机第三章有穷自动机南京航空航天大学计算机科学与技术学院胡军hujun.nju@139.com31七月2021南京航空航天大学计算机学院胡军2第三章有穷自动机1.1非形式化描述1.2有穷自动机的基本定义1.3非确定的有穷自动机1.4具有ε转移的有穷自动机1.5有穷自动机的应用1.6具有输出的有穷自动机（*)31七月2021南京航空航天大学计算机学院胡军31.1有穷状态系统指针式钟表共有12*60*60个状态小时×分钟×秒围棋共有3361个状态每一个格子：（空，黑，白）；格子数量：19行×19列某些电子产品中的开关电路，具有n个门的
2、开关网络有2n种状态“网上购物”系统（示例：）31七月2021南京航空航天大学计算机学院胡军42007年图灵奖模型检验（modelchecking）:基于自动机理论的形式化方法(formalmethods)E.ClarkEmersonSifakis31七月2021南京航空航天大学计算机学院胡军51.2有穷自动机的基本定义定义3.1一个有穷自动机(FiniteAutomata)简称FA，是一个五元组：M=(Q,∑,δ,q0,F)，其中（1）Q是有穷状态集；（States）（2）∑是有穷的输入字母表（Alphabet）（3）δ是转移函数，它将Q×∑
3、→Q(全映射)；（Transistonfunction）（4）q0∈Q，是初始状态；（Initialstate）（5）FQ，是终结状态集。（Acceptingstates）(终止状态，接受状态)上述定义的另一个说法：确定型的有穷自动机(DeterministicFiniteAutomata：DFA)31七月2021南京航空航天大学计算机学院胡军6DFA例子q0q1q21000,11字母表：S={0,1}状态集：Q={q0,q1,q2}初始状态：q0终结状态:F={q0,q1}状态集输入01q0q1q2q0q1q2q2q2q1转换函数表d:**→
4、问题：1.接受什么特征的字符串？2.状态q2起什么作用？31七月2021南京航空航天大学计算机学院胡军7这两个DFA所接受的字符串集合分别是什么？DFA例子q0q1baabS={a,b}q0q1q2q3q4aaaaabbbbbS={a,b}31七月2021南京航空航天大学计算机学院胡军8设计一个DFA(字母表为{0,1}),接受如下字符串：设计一个DFA(字母表为{0,1}),接受如下特征的字符串：最多有三个1.q0q1011q20q31q4+0,1010DFA例子L={010,1}qeq0q1q01q010qdie0,10100,11010,
5、131七月2021南京航空航天大学计算机学院胡军9设计一个DFA(字母表为{0,1}),接受所有结尾是01的字符串。提示：DFA得记住读入字符串的最后两位。DFA例子qe01q0q1q00q10q01q110101001110031七月2021南京航空航天大学计算机学院胡军10设计一个DFA(字母表为{0,1}),接受所有结尾是101的字符串。DFA例子31七月2021南京航空航天大学计算机学院胡军11例3.1给出一个有穷自动机Ｍ=({q0,q1,q2,q3},{0,1},δ,q0,{q0})其中：转移函数δ具体定义如下：δ(q0,1)=q1δ
6、(q0,0)=q2δ(q1,1)=q0δ(q1,0)=q3δ(q2,1)=q3δ(q2,0)=q0δ(q3,1)=q2δ(q3,0)=q1→*DFA例子31七月2021南京航空航天大学计算机学院胡军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)=δ(
7、δ(δ((q0,ε),0),1),0)=δ(δ(δ(q0,0),1),0)=δ(δ(q2,1),0)=δ(q3,0)=q1。31七月2021南京航空航天大学计算机学院胡军13有穷自动机的基本定义从δ到的扩充是很自然的，δ就是的特例（当
8、x
9、=1时）。今后在提到FA的转移函数时，不再强调这种写法，一律用δ表示，即δ的第二个变元既可以是单个字符也可以是一个字符串。31七月2021南京航空航天大学计算机学院胡军14有穷自动机模型开始时，“读头”指向带上的第一个输入符号，控制器中放的是FA的初始状态。然后，依据转移函数δ做动作：若控制器中的当前状态是q
10、，且“读头”指向带上符号为a，则控制器中状态将变成p=δ(q,a)，且“读头”向右移指向带上下一个符号，如此可以继续进行下去。(注意：读头不能回头，只
