第2章 节 形式语言的基本知识.pptVIP

2型（上下文无关）文法 文法G[S]： S→0A|1B A→1S|1 B→0S|0 该文法产生的语言为：L(G[S])={anbn|n≥1} （右线性） P： A:=a 或 A::=aB 其中 A、B∈ VN a∈ VT 3型语言：L3 又称正则语言 . 3型文法称为正则文法。它是对2型文法进行进一步限制。 左线性 和右线性文法是相互等价的 （左线性） P： A:=a 或 A::=Ba 其中 A、B∈ VN a∈ VT 3型文法： G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0 G[I]： I → lT I → l T → lT T → dT T → l T → d 例：3型文法 有关文法的实用限制 1、 若文法中有如U::=U的规则，则这就是有害规则，它会引 起二义性，而无任何用处。 例如存在U::=U， U::= a | b,则有两棵语法树： U a U U a 文法中不能含有有害规则和多余规则 无符号整数 数字串 数字串 数字 数字数字 1 数字 1 0 (6) == == (1) == (3) (5) == == (2) 当符号串已没有非终结符号时，推导就必须终止。因为 终结符不可能出现在规则左部，所以将在规则左部出现的符 号称为非终结符号。 例如：G[无符号整数] (1) 无符号整数 → 数字串 (2) 数字串 → 数字串 数字 (3) 数字串 → 数字 (4) 数字 →0 | 1 | 2 | 3 | …… | 9 如果存在直接推导序列： x ? y0 ? y1 ? y2…yn=y 则称这个序列是一个从x至y的长度为n（n0）的推导，或称y归约到x，记作x y。 若有x y，或x=y，则记作x y。 ＋ = ＋ = * = 例：x ? S ? SD ? LD ? aD ? a1=y G[S]： S→L|SL|SD L→a|b|…|z D→0|1|…|9 ＋ = 记作x y或记作x y * = 文法G[S] （1）句型：x是句型 ? S ? α,且α ∈V*； （2）句子：x是句子 ? S ? α, 且α, ∈VT*； （3）语言：L（G[S]）={α | α ∈VT*,S ? α }； + + 文法G[S]所产生的 所有句子的集合 * 句子是所有终结符 号组成的句型 语言的形式定义 G[E]： E→E+E|E*E|(E)|i 句型： E+E E+E*E E+E*i E+i*i 句子： i+i i*i i+i*i (i+i)*i 形式语言理论可以证明以下两点： （1）G →L（G）； （2）L(G)→G1，G2，……，Gn； 已知文法，求语言，通过推导； 已知语言，构造文法，无形式化方法，更多是凭经验 例：G[S] S ::= aSb |ab 求其所产生的语言。 若S ::= aSb | ε ，如何？ L(G[S])={anbn|n≥1} L(G[S])={anbn|n≥0} 已知文法，求语言，通过推导 课堂练习1：G[S] S ::= bA A ::= aA|a L(G[S])={ban|n≥1} 课堂练习2：G[S] S ::= AB A ::= aA|a B ::= bB|b L(G[S])={ambn|m,n≥1} 例：{abna|n≥1},构造其文法 定义. G和G’是两个不同的文法，若 L(G) = L(G’) , 则G和G’为等价文法。 若n≥0，如何？ 课堂练习3：{anbnci |n≥1,i ≥0},构造其文法 G[S]： S →AB