有穷自动机,编辑原理.pdfVIP

3.3 有穷自动机 第 三 有穷自动机(也称有限自动机)作为一种 别装置，它能准确地识别正规集，即识别正规文法所定义的语言 和正规式所表示的集合。 元 有穷自动机分为两类： 元 ～ 确定的有穷自动机和不确定的有穷自动机 目词 关于有穷自动机我们将讨论如下问题 录 法 确定的有穷自动机DFA 分 不确定的有穷自动机NFA 析 NFA的确定化 DFA的最小化 1.确定的有穷自动机 （DFA ） 1.DFA定义： 一个确定的有穷自动机（DFA）M是一个五元组：M= （K，Σ，f，S，Z）其中 1.K是一个有穷集，它的每个元素称为一个状态； 2.Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表 3. f是转换函数，是在K×Σ→K上的映射，即，如 f （ki，a）=kj，（ki K，kj K）就意味着，当前状态为 ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态； 4. S K是唯一的一个初态； 2.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 3.DFA状态图表示 假定DFA M含有m个状态，n个输入字符，那么这个状态图含有m个结点，每个结点最多有n个弧射出，整个图含 有唯一一个初态结点和若干个终态结点，初态结点冠以双箭头“=”或标以“-”，终态结点用双圈表示或标 以“+”，若 f(ki ,a)=kj，则从状态结点ki到状结点kj画标记为a的弧； 4.DFA矩阵表示 一个DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字 符列下的新状态，即k行a列为f (k,a)的值。用双箭头“=”标明初态；否则第一行即是初态，相应终态行在表 的右端标以1，非终态标以0。 5.DFA所接受 将转换函数进行扩充 一个输入符号串t，（将它表示成Tt1的形式，其中T ∈∑，t1 ∑*）在DFA M= （K，Σ，f，S，Z）上运行的 定义为：f （Q， Tt1）=f （f （Q，T），t1）其中Q K 例：证明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属于终态。 得证。 K:=S; c:=getchar; while ceof do { K:=f(K,c); c:=getchar; }; if K is in Z then return ( “yes”); else return ( “no”); 6.DFA 的确定性 DFA的确定性表现在转换函数f:K×Σ→K是一个