形式语言与自动机理论基础 2025/3/3

文法的定义一个文法G是一个四元组G(,,S,P)一个非空有限的终极符号集合。它的每个元素称为终极符号或终极符一般用小写字母表示。终极符号是一个语言不可再分的基本符号。一个非空有限的非终极符号集合。它的每个元素称为非终极符号或非终极符一般用大写字母表示。V是文法G的符号集则V∪∩S一个特殊的非终极符号称为文法的开始符号或识别符号。开始符号S必须至少在某个产生式的左部出现一次。P产生式的有限集合。产生式也成为产生规则或简称为规则产生式形式α-β等其中α称为产生式的左部α并且至少含有一个非终极符β称为产生式的右部β-或::读作定义为或由...组成。α是由β组成的文法分类0型文法短语型文法设文法G(,,S,P)如果对P中每一条产生式α-β不加限制即并且至少有一个非终极符则称G为0型文法或短语型文法。1型文法上下文相关文法设文法G(,,S,P)除且S不出现在任何产生式的右侧外如果对P中的每条产生式均限制为形如其中则称文法G为1型文法或上下文相关文法。这种文法意味着终极符A只有在α和β这样的一个上下文环境中才可以被替换为γ显示了上下文相关的特点。2型文法上下文无关文法设文法G(,,S,P)如果对P中的每条产生式均限制为形如其中则称G为2型文法或上下文无关文法。在2型文法中用α取代非终极符A与A所在上下文无关所以称之为上下文无关文法。3型文法线性文法、正则文法或正规文法设文法G(,,S,P)如果对P中的每条产生式均限制为形如或其中则称G为3型文法。上述形式的3型文法也称为右线性文法3型文法还有另一种形式称为左线性文法。如果对文法G的每条产生式形如或其中称该3型文法为左线性文法。上述四类文法从0型文法到3型文法对产生式的限制是逐步增强的而描述语言的能力是逐步减弱其后一类都是前一类的子集。四类文法之间的关系可以表示为0型文法1型文法2型文法3型文法对于每一型文法都有一类自动机和它的描述能力等价对应关系如下0型文法对应图灵机TM1型文法对应线性有界自动机LBA2型文法对应下推自动机PDA3型文法对应有限自动机FA在编译技术中通常用3型文法来描述高级程序设计语言的词法部分然后用有限自动机FA来识别高级语言的单词。今后对“文法”一词如无特殊说明则均指上下文无关文法。总结直接看长得像不像0型文法α-β1型文法2型文法左部只有一个非终极符右部终极符和非终极符3型文法或、或产生式的右部至多有两个符号且满足下面的形式之一、其中推导和归纳1.直接推导2.直接推导序列3.最左推导在推导过程中总是对当前符号串中最左的非终极符进行替换称为最左推导。4.最右推导在推导过程中总是对当前符号串中最右的非终极符进行替换称为最右推导。5.句型6.句子显然。句子是句型的特例只含有终极符的句型就是句子。文法G的句子的全体称为它所产生的语言记作L(G)。最右推导也称为规范推导。仅用规范推导得到的句型称为规范句型。规范推导的逆过程称为规范规约。7.短语一棵树及其子树包含的所有叶节点组成的符号串。8.直接短语简单短语只包含叶节点的子树其叶节点组成的符号串。9.句柄最左端的简单短语。题目语法树与文法二义性前面介绍了句型、推导等概念。下面介绍一种上下文无关文法的句型推导过程的直观描述方法即语法树也称推导树、生成树、分析树。语法树例最左推导最右推导树和e一样既非最左也非最右推导树和e一样另一种不同的最左推导总结生成的树可能一样也可能不一样。文法二义性对一个文法G如果至少存在一个句子有两棵或两棵以上不同的语法树则称该句子是二义性的。包含有二义性句子的文法称为二义性文法。若一个文法中存在某个句子它有两个不同的最左或最右推导则这个文法是二义性的。等价性定义可以有两个文法和一个有二义性另一个没有二义性但却有即这两个文法是等价的它们所产生的语言相同。文法的二义性是不可判断的即不存在一个算法它能在有限步骤内确切地判定一个文法是否是二义的。文法等价变换在LR类语法分析中为了便于控制分析过程的结束通常要求文法具有唯一的开始符并且开始符不出现于任何产生式的右部。如果不满足需要对原文法进行等价变换为此引入以下定理定理1对任一文法都可以构造文法使得且有这样的特点文法的开始符唯一并且不出现于任何产生式的右部。证明假设S是的开始符则只要在中扩充一条新产生式即可其中Z是新的开始符。令这样扩充后的文法为它显然满足定理的要求。定理2消除空产生式对于任一文法()则可构造文法使得并且中并无空产生式。定理3消除不可达产生式对任一文法都可以构造文法使得并且的每个非终极符必出现在某个句型中。定理4对任一文法都可以构造文法使得并且中没有特型产生式(左右都是非终结符)。例设有如下文法P19 还有几道例题有限自动机FA有限自动机分为确定有限自动机DFA和非确定有限自动机NFA。确定有限自动机只有进入Z终止状态时有限自动机识别/接受当前处理字符串并不是进了这个状态就要终止了终止状态也叫接受状态。确定有限自动机还可以用关系矩阵来表示也叫(状态)转换矩阵。第一列元素与确定有限自动机的状态集S相对应第一行的元素与确定有限自动机的有穷字母表相对应矩阵中的其他元素表示确定有限自动机的状态转换函数。开始终止*或-为什么只能是aba?因为别的就跑进“死胡同”了又不能终止又走不出来。总结DFA确定有限自动机为啥确定初始状态唯一映射是单值函数没有输入为的边即不接受没有任何输入就转换的情况非确定有限自动机接收一个字符允许跳转到多个后继状态。例总结非确定有限自动机NFA状态转换函数可为多值函数一个状态接受同一个输入字符可以转向多个不同后继状态。允许有多个开始状态。允许有空边即在没有任何输入的情况下允许进行状态转换。DFA与NFA的等价对于给定的有限自动机和如果则称有限自动机和等价。定理对于任何一个NFA M都存在一个DFA M使得。例NFA状态转换矩阵和等价的DFAPS{24567}怎么来的{12}经过a得到的{245}以及{245}的闭包经过{24567}合起来就是{24567}DFA I列的12345怎么来的分别用12345代表{12}{24567}{38}{389}{9}这5个状态子集。如下图红色部分正规式转化为NFANFA转化为DFA_哔哩哔哩_bilibiliDFA的化简对一个NFA把它等价变化为DFA后得到的DFA所具有的状态数可能并不是最小的。那么有没有一个最小的DFA呢这就是有限自动机的最简或最小化问题。一个确定有限自动机M的化简是指寻找一个状态数最少的DFA M使得L(M)L(M)定义1设DFA M的两个不同状态和如果对任意输入的符号串x从和出发总是同时到达接受或拒绝状态中则称和是等价的。如果和不等价则称和是可区分的。所接受的符号相同。显然DFA的终止状态和非终止状态是不等价的。定义2从有限自动机的初始状态开始任何输入序列都不能到达的那些状态称为无关状态。定义3如果DFA M没有无关状态也没有彼此等价的状态则称DFA M是最小的或规约的。