软件开发环境国家重点实验室1第二章 符号语言与形式文法第二章 符号语言与形式文法字母表、字符串及其集合符号语言及其运算性质形式文法及其派生语言形式文法的构成与等价形式文法的乔姆斯基体系定义 2.1 字母表是一个非空有限 集合，通常记作∑，其中元素称为字母表的字符3字母表及其字符特点： 1、字母表具有非空性和有穷性；2、字符具有不可分性 - 整体性；3、字符具有可区分性 - 可辨认性字母表与字符串例：考察以下字母表：∑ 1 = { aa, ab, bb }： 是字母表，其中， aa 不可拆分∑ 2 = { a, a‘, b, b’ }： 是字母表，其中， a, ‘ 不可拆分∑ 3 = { a, b, a }： 不是字母表，两个 a 无法区分字母表与字符串定义 2.2 设∑ 1，∑ 2 是两个字母表，∑ 1，∑ 2的乘积定义为∑ 1∑ 2 = { ab | a ∈∑ 1 ∧ b ∈∑ 2}例：1、 { 0, 1 } { a, b, c } = { 0a, 0b, 0c, 1a, 1b, 1c };2、 { a, b, c } { 0, 1 } = { a0, a1, b0, b1, 0c, c1 };3、 { aa, ab, bb } { 0, 1 } = { aa0, aa1, ab0, ab1, bb0, bb1 }显然，字母表的乘积不具有交换率。
字母表与字符串定义 2.3 设∑是一个字母表，∑乘积的 n 次幂可递归定义为：∑0= {ε }; ∑n= ∑n-1∑ , n≥ 1其中，ε是长度为 0 的字符串（空字符）注： {ε } 与空集 Φ的区别：1、ε是一个字符，用于标识长度为 0 的字符串；2、 {ε } ≠Φ： {ε } 是含有一个长度为 0 的字符串标记集合定义 2.4 设∑是一个字母表，∑的正闭包： ∑+= ∑∪∑2∪∑3∪ …. , ∑的克林闭包： ∑* = ∑0∪∑∪∑2∪∑3∪ …. ,字母表与字符串例：1、 { 0, 1 }+= { 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, ... };2、 { 0, 1 }*= {ε , 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, ... };3、 { a, b, c }*= {ε , a, b, c, aa, ab, ac, ba, bb, bc, …, aaa, … }字母表与字符串定义 2.5 设∑是一个字母表，∑*中的任一字符串 x 也叫做∑上的一个句子。
例：1、 { 0, 1 }*= {ε , 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, ... };2、 { a, b, c }*= {ε , a, b, c, aa, ab, ac, ba, bb, bc, …, aaa, … }例： | ab | = 2 , | aab | = 3, | an | = n , | a0| = |ε |= 08定义 2.6：字符串的长度设∑是一个字母表， ∀x ∈∑*，字符串 x 中字符出现的总个数叫做该串的长度，记作 | x |思考： | {ε } | = ？ | Φ | = ？字母表与字符串定义 2.7：字符串相等设 α和 β是任意两个字符串，则 α = β 当且仅当 | α | = | β |，并且组成 α的字符与组成 β的字符依次对应相同例：若 α = ab， β = ab，则 α = β；若 α = ab， β = ba，则 α≠β字母表与字符串定义 2.8 ：字符串的连接设 α和 β是∑* 上任意的两个字符串， α和 β的连接构成一个新句子，记作 α · β（简记为 αβ），该句子由串 α后直接接串 β组成。
字母表与字符串对于 n ≥ 0，字符串 α的 n 次幂为：（ 1） α0= ε；（ 2） αn = αn-1α例：设 ∑ = { 0, 1 }, x = 001, y = 1101；1、 x0= y0=ε ; 2、 xy = 0011101; 3、 x2= 0010014、 y4= 1101110111011101,字符串连接性质：对于∑ * 上任意字符串 x, y, z, 连接运算具有以下性质：1、结合律： ( xy ) z = x ( yz )2、左消去律： xy = xz ⇒ y = z 3、右消去律： yx = zx ⇒ y = z 4、唯一分解性：存在唯一确定的 a1, a2, …, an∈∑ , 使得x = a1a2…an5、单位元素： ε α = αε = α字母表与字符串设∑是一个字母表，任意字符串 x , y, z ∈∑*，且 x = yz，则称 y 是字符串 x 的前缀；如果 z ≠ε，则称 y 是 x 的真前缀 z 是 x 的后缀；如果 y ≠ε，则称 z 是 x 的真后缀定义 2.9： 字符串的前缀与后缀字母表与字符串例：求∑ = { a, b }上句子 abaabb 的前缀、后缀、真前缀、真后缀？前缀： ε , a, ab, aba, abaa, abaab, abaabb真前缀： ε , a, ab, aba, abaa, abaab后缀： ε , b, bb, abb, aabb, baabb, abaabb真后缀： ε , b, bb, abb, aabb, baabbε是任意字符串的前缀、后缀、子串。
定义 2.10：字符串的逆设ω = a1 a2 "an是任意字符串，称字符串 an "a2 a1是ω的逆，记作ωT13若ω = ωT，则称ω为回文字母表与字符串例：设ω = abcd，ωT= dcba例：字符串 0110110 和 deed 都是回文第二章 形式文法字母表与字符串符号语言以及其性质形式文法及其派生语言形式文法的构成与等价形式文法的乔姆斯基体系定义 2.11：符号语言设∑是任意字母表， ∀ L ⊆Σ*， L 称为字母表∑上的一个语言； ∀x ∈ L， x 叫做 L 的一个句子15符号语言及其运算性质例：设∑ = { 0, 1 }, 可定义∑上的不同语言如下：1、 { 0, 1 }; { 00, 11 }; { 0, 1, 00, 11, 01, 10 }; 2、 { 0, 1 }*; { 00, 11 }*; { 0, 1, 00, 11, 01, 10 }*; ……定义 2.12 ：语言的乘积设∑ 1 和∑ 2 是字母表， L1⊆Σ1*， L2 ⊆Σ2*， L1和 L2 的乘积L1L2= { xy | x ∈ L1∧ y ∈ L2 }是字母表∑ 1 ∪∑ 2 上的一个语言。
例 : 设 L1 = { ab， ac }, L2 = { e， bc }, 有L1L2 = { abe， abbc， ace， acbc }性质：语言的乘积满足结合律符号语言及其运算性质定义 2.13 ：语言的幂设有字母表∑， ∀ L ⊆Σ*， L 的 n 次幂是一个语言：（ 1）当 n = 0 时， Ln= L0= {ε } （ 2）当 n ≥ 1时， Ln= Ln-1 LL的正闭包 L+ 是一个语言：L+= L ∪ L2∪ L3∪ L 4 ∪ …L的克林闭包 L* 是一个语言：L* = L0∪ L ∪ L 2∪ L3∪ L4∪ …符号语言及其运算性质例：设∑ = { 0, 1 }, 分析下列语言句子的结构特征1、 有穷语言 ？无穷语言 ?2、 L5L7= L6？ L5L7= L8？L9= L10 ？3、 L6⊆ L5L7？ L9 ⊆ L10？L6⊆ L11？2、语言条件特征的细微差别，可导致很大的语言结构差别3、按照乔姆斯基分类法： L1-L5, L7, L8, L10, L12–3 型语言； L6, L11-2 型语言； L 9–1 型语言 符号语言及其运算性质定理 1.1 ：设 A、 B、 C、 D 是 ∑上任意语言，有1） A∅ = ∅A = ∅2） A{ ε } = { ε }A = A3）（ AB） C = A（ BC）4）若 A ⊆ B 和 C ⊆ D，有 AC ⊆ BD5） A（ B ∪ C） = AB ∪ AC19符号语言及其运算性质6）（ B ∪ C） A = B A ∪ C A7） A（ B ∩ C） ⊆ A B ∩ A C8）（ B ∩ C） A ⊆ B A ∩ C A9） Am An = Am+n10）（ Am ）n = Amn11）若 A ⊆ B，则 An ⊆ Bn20符号语言及其运算性质12） A* = { ε } ∪ A+ 13） An⊆ A*，其中， n ≥ 014） An ⊆ A+， 其中， n ≥ 115） A ⊆ A B ∗16） A ⊆ B ∗A17）若 A ⊆ B，则 A∗⊆ B∗21符号语言及其运算性质18）若 A ⊆ B，则 A+⊆ B+19） AA* = A*A = A+20）若 ε∈A，则 A∗= A+21）（ A∗）∗= A ∗A∗= A ∗22）（ A∗)*= （ A+）∗= A ∗23）（ A∗)+= A+A+= A+ 符号语言及其运算性质第二章 1节小结本节介绍：符号语言相关的基本概念，包括字母表、字符串及其运算、字母表上的符号语言、句子、语言的基本运算及其性质。
形式语言及其性质练习题（教材 P40）：题 21，题 28，题 30 – 3, 4, 8, 9，题 32思考题：题 24 – 题 27第二章 形式语言和形式文法字母表与字符串符号语言及其性质形式文法及其派生语言形式文法的构造与等价形式文法的乔姆斯基体系形式文法及其派生语言形式文法是生成符号语言的一种数学系统：用形式化的有穷描述手段描述符号语言的结构特征；生成语言的所有句子；判断所给符号串是否为语言句子，若不是，错在何处为此，需定义合式正确的形式文法定义 2.14：形式文法的一般性定义形式文法（简称文法）表现为一个四元组 G = ( V,T,P,S ), 其中，V：变元的非空有穷集；其中，每个语法变元代表一个语法范畴T：终极符的非空有穷集，V ∩ T = ∅P：产生式的非空有穷集，P 中元素一般形式为 α→β，读作：α 定义为 β ，或 α 可以是 β ；其中α∈（ V ∪ T ）+，且 α 中至少有 V 中一个元素出现；β∈（ V ∪ T ）∗S： S ∈ V，为开始符27形式文法及其派生语言约定 - 按以下方式使用 V ∪ T 中 符号：英文字母较为前面的大写字母，如 A， B， C， …，表示语法变量；英文字母较为前面的小写字母，如 a， b， c， …，表示终极符号；英文字母较为后面的大写字母，如 X， Y， Z， …，表示语法变量或终极符号英文字母较为后面的小写字母，如 x, y, z, …, 表示由终极符号组成的符号串西腊字母 α ， β， γ， …，表示语法变量或终极符号组成的符号串。
形式文法及其派生语言左部相同的产生式： α→β1， α→β2， …, α→βn 可写为 ： α→β1 | β2 | …| βn形式文法及其派生语言例：设有四元组G = （ { A, B, C, E }, { a, b, c }, { S → ABC | abc, D → e | a, FB→c, A→A, E→abc |ε }, S ) 是否为一合式文法？存在问题：1、变量 S， D 不在 V 中；2、终极符 e 不在 T 中；3、变量 F 不在 ( 。