编译原理第七讲讲述.ppt

关于有穷自动机我们将讨论如下题目 确定的有穷自动机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 的矩阵表示 练习 设ＤＦＡ　Ｍ＝（ ｛０，１，２， ３｝ ， ｛ａ，ｂ｝， δ ，０，｛３｝）其中 δ（０，ａ）＝１，δ（１，ａ）＝3 δ（２，ａ）＝１，δ（３，ａ）＝３ δ（０，ｂ）＝２，δ（１，ｂ）＝２ δ（２，ｂ）＝３，δ（３，ｂ）＝３ 构造ＤＦＡ　Ｍ状态转换图和状态转换矩阵 例 ?构造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　Ｍ ，使得L(M)=L(N)。 与上例等价的一个NFA.  NFA M 所识别的语言 对于Σ﹡中的任何一个串t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为ε的弧)等于t，则称t可为NFA M所识别(读出或接受)。NFA M所能接受的符号串的全体即NFA M所识别的语言记为 L(M)  注意：若M的某些结既是初态结又是终态结，