《形式语言与自动机》由会员分享，可在线阅读，更多相关《形式语言与自动机（89页珍藏版）》请在金锄头文库上搜索。
1、第2章 形式语言与自动机基 础知识点：文法的形式定义上下文无关文法、正规文法推导、短语、分析树、二义性有限自动机的形式定义自动机、文法、表达式等价性NFA的确定化、DFA的最小化形式语言与自动机基础2.1 语言和文法 2.2 有限自动机 2.3 正规文法与有限自动机的等价性 2.4 正规表达式与有限自动机的等价性 2.5 正规表达式与正规文法的等价性小 结22.1 语言和文法一、字母表和符号串二、语言三、文法及其形式定义四、推导和短语五、分析树及二义性六、文法的变换3一、字母表和符号串字母表 符号的非空有限集合 典型的符号是字母、数字、各种标点和运算符等 。 符号串 定义在某一字母表上 由该字
2、母表中的符号组成的有限符号序列 同义词：句子、字 符号串有关的几个概念n长度 符号串的长度是指中出现的符号的个数，记作 |。 空串的长度为0，常用表示。4n前缀 符号串的前缀是指从符号串的末尾删除0个或多 个符号后得到的符号串。如：univ 是 university 的 前缀n后缀 符号串的后缀是指从符号串的开头删除0个或 多个符号后得到的符号串。如：sity 是 university 的后缀n子串 符号串的子串是指删除了的前缀和/或后缀后 得到的符号串。如：ver 是 university 的子串n真前缀、真后缀、真子串 如果非空符号串是的前缀、后缀或子串，并且 ，则称是的真前缀、真后缀、或
3、真子串。n子序列 符号串的子序列是指从中删除0个或多个符号( 这些符号可以是不连续的)后得到的符号串。如：nvst5n连接 符号串和符号串的连接是把符号串加在符 号串之后得到的符号串 若=ab，=cd，则=abcd，=cdba。 对任何符号串来说，都有=n幂 若是符号串，的n次幂n 定义为：n个当n=0时，0是空串。 假如=ab，则有： 0= 1=ab 2=abab n=abababn个ab6二、语言语言：在某一确定字母表上的符号串的集合。 空集，集合也是符合此定义的语言。 这个定义并没有把任何意义赋予语言中的符号串 。 语言的运算：假设L和M表示两个语言nL和M的并记作LM：LM=s|sL
4、或 sMnL和M的连接记作LM：LM=st|sL 并且 tMnL的闭包记作L*：即L的0次或若干次连接。= L0L1L2L3 nL的正闭包记作L+：即L的1次或若干次连接。= L1L2L3L4 7nL=A,B, ,Z,a,b, ,z，D=0,1, ,9 可以把L和D看作是字母表 可以把L和D看作是语言n语言运算举例：n把幂运算推广到语言 L0=，Ln=Ln-1L，于是Ln是语言L与其自身的n-1 次连接。语言 描述LD 全部字母和数字的集合LD 由一个字母后跟一个数字组成的所有符号串的集合L4 由4个字母组成的所有符号串的集合L* 由字母组成的所有符号串（包括）的集合L(LD)* 以字母开头，
5、后跟字母、数字组成的所有符号串的集合D+ 由一个或若干个数字组成的所有符号串的集合 8三、文法及其形式定义n文法：所谓文法就是描述语言的语法结构的形式规则。n任何一个文法都可以表示为一个四元组G=(VT,VN,S, )VT是一个非空的有限集合，它的每个元素称为终结符号。VN是一个非空的有限集合，它的每个元素称为非终结符号。VTVN =S是一个特殊的非终结符号，称为文法的开始符号。是一个非空的有限集合，它的每个元素称为产生式。产生式的形式为： “” 表示 “定义为”（或“由组成”） 、(VTVN)* ，左部相同的产生式1、2、n可以缩写1|2|n “|” 表示 “或”， 每个i(i=1,2,n)
6、称为的一个候 选式9文法的分类根据对产生式施加的限制不同，定义了四类文法和相应的四种形式语言类。文法类型 产生式形式的限制 文法产生的语言类0型文法 其中 ,(VTVN)* 0型语言|0 1型文法，即 1型语言，即 上下文有关文法 其中 ,(VTVN)* 上下文有关语言| 2型文法，即 A 2型语言，即 上下文无关文法 其中 AVN，(VTVN)* 上下文无关语言3型文法，即 Aa或AaB（右线性），或 3型语言，即正规文法 Aa或ABa（左线性） 正规语言（线性文法） 其中 A,BVN， aVT10上下文无关文法及相应的语言n所定义的语法单位(或称语法实体)完全独立于这种 语法单位可能出现的
7、上下文环境n现有程序设计语言中，许多语法单位的结构可以用 上下文无关文法来描述。 例：描述算术表达式的文法G：G=(i,+,-,*,/,(,),) 其中： + | - | * | / | () | in语言L(G)是所有包括加、减、乘、除四则运算的算 术表达式的集合。11n如果用“:=”代替“”，这组产生式可以写为 ：:= + | - | := * | / | := () | in元语言： := 表示 “定义为” 或 “由组成 ”表示非终结符号 | 表示“或”BNF（Backus-Normal Form）表示法12文法书写约定n终结符号 次序靠前的小写字母，如：a、b、c 运算符号，如：+、-
8、、*、/ 各种标点符号，如：括号、逗号、冒号、等于号 数字1、2、9 黑体字符串，如：id、begin、if、thenn非终结符号 次序靠前的大写字母，如：A、B、C 大写字母S常用作文法的开始符号 小写的斜体符号串，如：expr、term、factor、 stmt13n终结符号串 次序靠后的小写字母，如：u、v、zn文法符号串 小写的希腊字母，如：、n可以直接用产生式的集合代替四元组来描述文法， 第一个产生式的左部符号是文法的开始符号。n文法符号 次序靠后的大写字母，如：X、Y、Z14四、推导和短语例：考虑简单算术表达式的文法G：G=(+，*，（，），i,E，T，F,E,)： E E + T
9、 | TT T * F | FF（E）| in文法所产生的语言 从文法的开始符号出发，反复连续使用产生式对 非终结符号进行替换和展开，就可以得到该文法定义的 语言。15推导假定A是一个产生式，和是任意的文法符号串， 则有： A n “” 表示 “一步推导”即利用产生式对左边符号串中的一个非终结符号进 行替换，得到右边的符号串。n 称A直接推导出n 也可以说是A的直接推导n 或说直接归约到A16从文法开始符号E推导出符号串i+i的详细过程如果有直接推导序列：12n 则说1推导出n，记作：1 n *“ ”表示0步或多步推导称这个序列是从1到n的长度为n的推导A 所用产生式 从E到 的推导长度E E
10、+T EE+T 1E+T T+T +T ET 2T+T F+T +T TF 3F+T i+T +T Fi 4i+T i+F i+ TF 5i+F i+i i+ Fi 6E E+T T+T F+T i+T i+F i+i 17最左推导最右推导如果 ，并且在每“一步推导”中，都替换中最左 边的非终结符号，则称这样的推导为最左推导。记作：*lm 如果 ，并且在每“一步推导”中，都替换中最右 边的非终结符号，则称这样的推导为最右推导。记作：*rm 最右推导也称为规范推导E E+T T+T F+T i+T i+F i+iE E+T E+F E+i T+i F+i i+i18句型句子 仅含有终结符号的句型
11、是文法的一个句子。 语言 文法G产生的所有句子组成的集合是文法G所定义的语言 ，记作L(G)。对于文法G=(VT,VN,S,)，如果S ，则称是当前文法 的一个句型。*若S ，则是当前文法的一个左句型，若S ，则是当前文法的一个右句型。*lm*rmL(G)= | S ，并且 VT* +19对于文法G=(VT,VN,S,)，假定是文法G的一个句型 ，如果存在：短语S A，并且 A *+则称是句型关于非终结符号A的短语。 如果存在：S A，并且 A *则称是句型关于非终结符号A的直接短语。一个句型的最左直接短语称为该句型的句柄。 例:ETT*FT*(E)F*(E)i*(E)i*(E+T)i*(T+
12、T)i*(F+T)i*(i+T) 20五、分析树及二义性n分析树n子树n子树与短语之间的关系n二义性21分析树n推导的图形表示，又称推导树。n一棵有序有向树，因此具有树的性质 ；n自己的特点：每一个结点都有标记。 根结点由文法的开始符号标记； 每个内部结点由非终结符号标记， 它的子结点由这个非终结符号的这次推 导所用产生式的右部各符号从左到右依 次标记； 叶结点由非终结符号或终结符号标 记，它们从左到右排列起来，构成句型 。 ETT*FT*(E)F*(E)i*(E)i*(E+T)i*(T+T)i*(F+T) i*(i+T)ETT * FF ( E )i E + TT F i ETT*FF*Fi*Fi*(E) i*(E+T)i*(T+T)i*(F+T)i*(i+T)22T子树E子树T子树ETT * FF ( E )i E + TT F i 子树n分析树中一个特有的结点 、连同它的全部后裔结点 、连接这些结点的边、以 及这些结点的标记。n子树的根结点的标记可能 不是文法的开始符号。n如果子树的根结点标记为 非终结符号A，则可称该子 树为A-子树。23直接短语短语句柄ETT * FF ( E )i E + TT F i 子树与短语的关系n一棵子树的所有叶
