编译原理第七讲讲述.ppt

  1. 1、本文档共96页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
编译原理第七讲讲述

关于有穷自动机我们将讨论如下题目 确定的有穷自动机DFA 不确定的有穷自动机NFA NFA的确定化 DFA的最小化 1.确定的有穷自动机DFA DFA定义: 一个确定的有穷自动机(DFA)M是一个五元组:M=(K,Σ,f,S,Z)其中 1.K是一个有穷集,它的每个元素称为一个状态; 2.Σ是一个有穷字母表,它的每个元素称为一个输入符号,所以也称Σ为输入符号表; DFA定义 3.f是转换函数,是在K×Σ→K上的单值映射,即,如 f(ki,a)=kj,(ki∈K,kj∈K)就意味着,当前状态为ki,输入符为a时,将转换为下一个状态kj,我们把kj称作ki的一个后继状态; 4.S∈K是唯一的一个初态; 5.Z? K是一个终态集,终态也称可接受状态或结束状态。 一个DFA 的例子: DFA M=({S,U,V,Q},{a,b},f,S,{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 的状态图表示 DFA 的矩阵表示 练习 设DFA M=( {0,1,2, 3} , {a,b}, δ ,0,{3})其中 δ(0,a)=1,δ(1,a)=3 δ(2,a)=1,δ(3,a)=3 δ(0,b)=2,δ(1,b)=2 δ(2,b)=3,δ(3,b)=3 构造DFA M状态转换图和状态转换矩阵 例 ?构造DFA作为一个奇偶校验器,识别0,1组成的含有奇数个1的符号串 DFA M 接受的语言 ∑*上的符号串t被DFA M接受 M=(K,Σ,f,S,Z) 若t? ∑*,f(S,t)=P,其中S为 M的开始状态,P ? Z,Z为终态集。 则称t为DFA M所接受(识别). 对于Σ﹡中的任何一个串t,若存在一条从某一初态结到某一终态结的道路,且这条道路上所有弧的标记字依序连接成的串等于t,则称t可为DFA M所识别(读出或接受)。DFA M所能接受的符号串的全体即NFA M所识别的语言记为 L(M) 例:证明t=baab被下图的DFA所接受。 f(S,baab)=f(f(S,b),aab) = f(V,aab)= f(f(V,a),ab) =f(U,ab)=f(f(U,a),b) =f(Q,b)=Q Q属于终态。 得证。 DFA M所能接受的符号串的全体记为L(M). 对于任何两个有穷自动机M和M′,如果L(M)=L(M′),则称M与M′是等价的.? 结论: ?上一个符号串集V???是正规的,当且仅当存在一个?上的确定有穷自动机M,使得 V=L(M)。 DFA的行为很容易用程序来模拟. DFA M=(K,Σ,f,S,Z)的行为的模拟程序 K:=S; c:=getchar; while ceof do {K:=f(K,c); c:=getchar; }; if K is in Z then return (‘yes’) else return (‘no’) DFA的确定性表现在 1)转换函数f:K×Σ→K是一个单值函数,也就是说,对任何状态k∈K,和输入符号a∈Σ,f(k,a)唯一地确定了下一个状态。从状态转换图来看,若字母表Σ含有n个输入字符,那末任何一个状态结点最多有n条弧射出,而且每条弧以一个不同的输入字符标记。 2)初始状态是唯一的 不确定的有穷自动机NFA 定义 NFA M=?K,?,f,S,Z?,其中K为状态的有穷非空集, ? 为有穷输入字母表,f为K? ?* 到K的子集(2 K)的一种映射,S?K是初始状态集,Z ?K为终止状态集. 例子 NFA M=({S,P,Z},{0,1},f,{S,P},{Z}) 其中 f(S,0)={P} f(Z,0)={P} f(P,1)={Z} f(Z,1)={P} f(S,1)={S,Z} 状态图表示 矩阵表示 矩阵表示 f为K? ?* 到K的子集(2 K)的一种映射 具有?转移的不确定的有穷自动机 有如下定理: 对任何一个具有?转移的不确定的有穷自动机NFA  N,一定存在一个不具有?转移的不确定的有穷自动机NFA M ,使得L(M)=L(N)。 与上例等价的一个NFA. NFA M 所识别的语言 对于Σ﹡中的任何一个串t,若存在一条从某一初态结到某一终态结的道路,且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为ε的弧)等于t,则称t可为NFA M所识别(读出或接受)。NFA M所能接受的符号串的全体即NFA M所识别的语言记为 L(M) 注意:若M的某些结既是初态结又是终态结,

文档评论(0)

shuwkb + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档