资源描述：
《形式语言与自动机基础ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章形式语言与自动机基础2.1文法和语言2.2有限自动机2.3正规式与有限自动机Ch2形式语言自动机理论基础2.2自动机基础第2章形式语言与自动机基础2.2有限自动机基础2.2.1确定的有限状态自动机(DFA)2.2.2非确定的有限状态自动机(NFA)2.2.3NFA确定化2.2.4DFA化简Ch2形式语言自动机理论基础2.2自动机基础定义2.24一个确定的有限自动机M(DFAM)是一个五元组M=（Q,,f,q0,Z）Ch2形式语言自动机理论基础2.2自动机基础2.2.1确定的FA（DFA）确定的有限自动机（
2、DFA）(DFA：DeterministicFiniteAutomaton)其中：Q：状态的有限集合，每个元素qi(qiQ)称为一个状态。：输入字符的有限集合(或有穷字母表)。每个元素是一个输入字符。Ch2形式语言自动机理论基础2.2自动机基础2.2.1确定的FA（DFA）q0：M的唯一初态（也称开始状态），q0Q。f：状态转换函数：从QQ的映射。例如,f（p,a）=q,q、pQ,a。表示了状态p在输入字符a之后转入状态q。q也称为p的后继状态。Z：M的终态集（或接受状态）ZQ。Ch2形式语言
3、自动机理论基础2.2自动机基础2.2.1确定的FA（DFA）二.DFA的等价表示DFA形式定义状态转换图状态转换表例2.20:DFAM=（{0,1,2,3},{a,b},f,0,{3}）f（0,a）=1f（0,b）=2f（1,a）=3f（1,b）=2f（2,a）=1f（2,b）=3f（3,a）=3f（3,b）=3Qq0ZfCh2形式语言自动机理论基础2.2自动机基础2.2.1确定的FA（DFA）状态转换图表示DFA状态图Q状态结点弧上标记(边权值)f带权值的有向边q0Zq0ZCh2形式语言自动机理论基础2.2
4、自动机基础2.2.1确定的FA（DFA）0123aabbab状态转换图表示DFAM=({0,1,2,3},{a,b},f,0,{3}）f（0,a）=1f（0,b）=2f（1,a）=3f（1,b）=2f（2,a）=1f（2,b）=3f（3,a）=3f（3,b）=3abCh2形式语言自动机理论基础2.2自动机基础2.2.1确定的FA（DFA）二.DFA的等价表示DFA形式定义状态转换图状态转换表例2.20:DFAM=（{0,1,2,3},{a,b},f,0,{3}）f（0,a）=1f（0,b）=2f（1,a）=3f（
5、1,b）=2f（2,a）=1f（2,b）=3f（3,a）=3f（3,b）=3Qq0ZfCh2形式语言自动机理论基础2.2自动机基础2.2.1确定的FA（DFA）状态转换表表示ab0121322123*33fQq0ZDFAM=({0,1,2,3},{a,b},f,0,{3}）f（0,a）=1f（0,b）=2f（1,a）=3f（1,b）=2f（2,a）=1f（2,b）=3f（3,a）=3f（3,b）=3Ch2形式语言自动机理论基础2.2自动机基础2.2.1确定的FA（DFA）三.DFA的识别机制如果存在Q中的状态
6、序列p0，p1，，pn，满足下列条件：p0＝q0f（pi，wi＋1）＝pi＋1，i＝0，1，，n－1pnZ则M接受（识别）。确定的有限自动机M=（Q,,f,q0,Z）接受或识别字母表上的字符串＝w1w2wn的意义：Ch2形式语言自动机理论基础2.2自动机基础2.2.1确定的FA（DFA）从状态图出发可以更形象地进行描述。若存在一条从初态结点到某一终态结点的路径，且在这条路径上所有弧的标记连接成的字符串等于，则称为DFAM所识别(接受)。确定的有限自动机M识别的字符串的全体称为M识别的语言，记为
7、L(M)。L(M)={
8、*f(q0,)Z}特例的是，若M的初态结点同时又是终态结点，则空串ε为M所识别。设＝a1a2an-1an，f(q0,)=f(f(f(f(q0,a1,),a2),,an-1),an)确定的有限自动机M=（Q,,f,q0,Z）接受或识别字母表上的字符串＝w1w2wn的意义：根据串沿着序列（路径）p0，p1，，找到pn，判断pn是否属于终态集。判断寻找Ch2形式语言自动机理论基础2.2自动机基础2.2.1确定的FA（DFA）具体识别方法：如果存在Q中的状态序列
9、p0，p1，，pn，满足下列条件：p0＝q0f（pi，wi＋1）＝pi＋1，i＝0，1，，n－1pnZ则M接受（识别）。Ch2形式语言自动机理论基础2.2自动机基础2.2.1确定的FA（DFA）例2.21:分析下面描述的DFAM1。DFAM1=({qee,qoe,qeo,qoo}，{0,1}，f，qee，{qee})其中：f(qee，0)=qoef(qee，1)=
