有限自动机.ppt
《有限自动机.ppt》由会员分享,可在线阅读,更多相关《有限自动机.ppt(30页珍藏版)》请在三一文库上搜索。
1、有限自动机(Finite Automata),描述程序设计语言中的单词的识别过程。 主要内容: 确定有限自动机DFA(Deterninistic FA) 确定有限自动机DFA的实现 非确定有限自动机NFA(Nondeterninistic FA) NFA到DFA的转换 DFA的化简,确定有限自动机DFA,确定有限自动机DFA为一个五元组 (,SS,S0,f,TS),其中: 是一个有穷字母表,它的每个元素称为一个输入字符; SS是一个有穷集,它的每个元素称为一个状态; S0 SS是唯一的一个初始状态; f是在 SS SS上的转换函数 TSSS,是一个终止状态集,又称为接受状态集,DFA的两种表示
2、方式,状态转换图: 结点表示状态,转换边表示转换函数,边 的箭头方向指向转换函数中定义的转换方 向。标识出初始状态和终止状态。 状态转换表: 可用二维数组描述。标识出初始状态和终 止状态。 Trans( SI ,a) SJ,一个DFA的例子,DFA M=( a,b, S,U,V,Q, S, f, Q ), 其中 f 定义为: f ( S, a )=U f ( V, a )=U f ( S, b )=V f ( V, b )=Q f ( U, a )=Q f ( Q, a )=Q f ( U, b )=V f ( Q, b )=Q,状态转换表,DFA接受的字符串,对于*中的任何字符串t,若存在一
3、条从初始结点到某一终止结点的路径,且这条路上所有弧的标记符连接成的字符串等于t,则称t可为DFA M所接受(识别)。 DFA M 所能接受的字符串的全体记为L(M).,DFA的确定性,初始状态唯一。 转换函数f:SSSS是一个单值函数,也就是说,对任何状态SSS,和输入符号a , f(S,a)唯一地确定了下一个状态。即转换函数至多确定一个状态。 没有空边。即没有输入为(),DFA的实现1,状态转换表的形式:(数组T存放转换函数) 1.当前状态State置为初始状态 2.读一个字符 CurrentChar 3.如果CurrentCharEof并且 T(State,CurrentChar)erro
4、r 则当前状态转为新的状态T(State,Current), 读下一字符。重复第3步工作。 4.如果当前字符为Eof并且当前状态属于终止状态,则接受当前字符串,程序结束。否则报错 特点: 程序短小,但占用存储空间多,b,DFA的实现2,状态转换图的形式: 每个状态对应一个带标号的case语句 转向边对应goto语句 特点: 程序长,但占用存储空间少,i,j,k,a,Li: case CurrentChar of a :goto Lj b : goto Lk other : Error( ),非确定有限自动机NFA,定义1:一个非确定有限自动机(NFA)A是一个五元组A=(,SS,S0,f,TS
5、).其中 是字母表 SS是状态集 S0是初始状态集 f是转换函数,但不要求是单值的 f: SS () 2SS TS是终止状态集,非确定有限自动机NFA,定义2:设A是一个NFA,A= (,SS,S0,f,TS) 则定义L(A)为从任意初始状态到任意终止状态所接受的字符串。 L(A)=|s0s, s0 S0 sTS 定义3:设A1和A2是同一个字母表上的自动机,如果有L(A1)=L(A2),则称A1和A2等价。,NFA到DFA的转换,定理 对于每一个非确定自动机A,存在一个确定自动机A,使得L(A)=L(A). 转换: 符号合并 同一状态的不同输出边标有相同的字符。 合并 含有边,NFA到DFA
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 有限 自动机
链接地址:https://www.31doc.com/p-3297683.html