《编译原理》课程简介 (13).pdf
编 译 原 理 C O M P I L A T I O N P RIN C IP LE 第三章 词法分析3.3.2 正规式与有限自动机3.3.2 正规式与有限自动机一、基本概念二、确定有穷状态自动机（DFA）三、非确定有穷状态自动机（NFA）四、正规式和有限自动机的等价性五、DFA的化简3.3.2 正规式与有限自动机p一个确定的有穷自动机（DFA）D是一个五元组：D=（K，M，S，F）其中nK：有穷非空的状态集合；n：有穷非空的输入符号字母表；nM：转换函数，是在KK上的映像，即，如 M(ki,a)=kj,(kiK,kjK)就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；nSK是唯一的一个初态；nF K是非空的终态集合。确定型有穷状态自动机 3.3.2 正规式与有限自动机n注：一个DFA可表示为一个状态转换矩阵，行表示状态，列表示输入字符，矩阵元素Ms,a的值为(s,a)。确定型有穷状态自动机 DFA M=(0,1,2,a,b,0,2)，其中(s,a)=S,(s,b)=2,s=0,1,2例例p 例23.3.2 正规式与有限自动机确定型有穷状态自动机 有一DFA M=(0,1,2,a,b,f,0,2)，其中f(s,a)=S,f(s,b)=2,s=0,1,2例例3.3.2 正规式与有限自动机p一个DFA M也可用一张状态转换图表示，DFA的每个状态对于状态转换图的一个接点，图中箭弧上的标记为输入字符，若(s,a)=S，则从状态s画一条箭弧到S，弧上标记为a。pDFA M识别的字的全体记为L(M)。p对*中的任何字，若存在一条从初态到某一终态的道路，且这条路上所有弧上标记连接成的字等于，则称可为DFA M所识别，或称DFA M可读出（或接受、识别）字。确定型有穷状态自动机 3.3.2 正规式与有限自动机p如果一个DFA M的输入字母表为，则我们也称M是上的一个DFA。可以证明：上的一个子集是正规的，当且仅当存在上的DFA M，使得V=L（M）。pDFA的确定性表现在映射：SS是一个单值函数。也就是说，对任何状态sS和输入符号a，(s,a)唯一地确定了下一状态。p特别地，若DFA M的初态同时又是终态，该DFA M可识别空字。p显然，若DFA M中字母表含n个字母，则任何一个状态顶多只有n条发出弧。确定型有穷状态自动机 3.3.2 正规式与有限自动机l从状态转换图构造有穷状态自动机p例如：从下面状态图构造DFAnDFA D=（S，Z，A，B，a，b，M，S，Z）n其中M定义为：M（S，a）=AM（S，b）=BM（A，a）=ZM（A，b）=BM（B，a）=AM（B，b）=ZM（Z，a）=Z3.3.2 正规式与有限自动机l运行DFA与识别一个字符串p扩充的映像M定义：M(R,)=RM(R,Tt)=M(M(R,T),t)，其中t*，Tp以上两个式子的含义是什么？p定义：对于某DFA D=（K,M,S,F），如果M(S，t)=P,PF，则称符号串t可被DFA D所接受。p运行一个DFA的过程：识别一个符号串是否被接受3.3.2 正规式与有限自动机p如前例：DFA D=（S，Z，A，B，a，b，M，S，Z）M（S，a）=AM（S，b）=BM（A，a）=ZM（A，b）=BM（B，a）=AM（B，b）=ZM（Z，a）=Zp则：M(S,ababaa)=M(M(S,a),babaa)=M(A,babaa)=M(M(A,b),abaa)=M(B,abaa)=M(A,baa)=M(B,aa)=M(A,a)=Z举 例3.3.2 正规式与有限自动机l如何在计算机内表示映像？p 映像M：含义？p 映像在计算机内的表示法：矩阵表示法表结构表示法3.3.2 正规式与有限自动机lDFA 的矩阵表示法abSABAZBBAZZZ状 态字 符矩阵行代表状态，列代表输入字符,矩阵元素是映像得到的新状态。|编译原理谢 谢Thanks
