- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
若x=abbc,y=abbc 则x=y; 若x=abbc,y=abbcc,则x≠y
2）符号串长度：符号串‘x’所包含的符号个数。用‘|x|’表 示。 |abcd|=4; | |=0;
3）符号串的连结：设x,y是∑上的两个符号串，把y的所有符 号相继写在符号串x的最后符号之后所得到的新符号串，称为 x与y的连接，用xy表示。
例：试设计一个表示所有标识符的文法
例：设字母表={0，1}，则+可描述为： +={0，1，00，10，11，01，000，100……} 若用A表示+，用A →0表示符号串0∈A，或A生成符号0， 符号“→”读作“生成”或“由⋯ ⋯组成” 则集合A可以表示成：
A →0 A →1 A →A0 A →A1
2.3.2 文法和语言的形式定义
：为某一字母表， L：一个语言， L* 2.3.1 形式语言
1.定义：序列的有穷集合。具体地说每个形式语言都是某个字母 表上按某种规则构成的所有符号串的集合，反之任何一个字母 表上符号串的集合均可以定义一个形式语言。
2.表示方法：
1）枚举法。当语言为有穷集合时使用。
2）文法描述。当语言为无穷集合时使用。
A2=AA={aa， ab， ba， bb} A3=A2A={aaa， aab， aba，abb ，baa ，bab ，bba ，bbb}
10）集合A的正闭包和闭包 定义：集合A的正闭包表示为A+: A+=A1 ∪A2 ∪… ∪ Ak … 定义：集合A的闭包符号记为A*（又称为反闭包或星闭 包）: A*=A0∪A1 ∪A2 ∪… ∪ Ak … 根据定义有： A*= A0∪ A+
例：abc 前缀：a,ab,abc ， ；后缀：c,bc,abc ，；
子串：a,ab,abc， c,bc, b ，
6）符号串集合的乘积 定义：设A，B为两个符号串集合，其乘积为 AB={xy|xA，yB} 例： A={ab,bc},B={ac,cb} 则AB={abac,abcb,bcac,bccb} ， AB≠BA 因为： x=x=x 所以有：{ }A=A { } =A;
例：若A={a,b}，则
A+=A1 ∪A2 ∪…={a,b,aa,ab,ba,bb,aaa,aab, aba,abb,baa,bab,bba,bbb,…} A*= A0∪ A+ ={ ,a,b,aa,ab,ba,bb,aaa,aab, aba,abb,baa,bab,bba,bbb,…}
2.3 文法和语言的形式定义
P={x| x∈自然数}
2）符号（字符）：字母表中的元素 ∑中的符号： a, b,c
3）符号串：符号的有穷序列 a, b,c,cabccad,ab, ba ε ：表示不含任何符号的符号串。
4）符号串集合：字母表上的若干个符号串组成的集合 A={a, aa, ba}
2.2.2 符号串的运算 1）符号串相等：设x,y是∑上的两个符号串，若x,y的相同位 置上的符号完全相同，则称x,y相同。
P={A → aa|aaB| bb|bbD B → aa|aaB
若P为A → aa|bb|Abb |A aa则不 正确
D→ bb|bbD}
或P={A → B|D
B → aa|aBa
D→ bb|bDb}
结论：1.对于一个给定的语言，描述该语言的文法不是唯一的
2.G和G,是两个不同的文法，如果他们描述的语言相同，那么 称G和G,为等价文法。
第二章 文法和形式语言
对语言的非形式化描述从三个因素考虑 1.语法：对语言数据结构的定义 2.语义：语言的含义 3.语用：从用户的角度去描述语言 形式化的方法：是用一套带有严格规定的符号体系来 描述问题的理论和方法。
2.2 字母表和符号串的基本概念
2.2.1 字母表和符号串 1）字母表：元素的非空有穷集合 ∑={a, b,c} ，V={0, 1}，
2.文法
文法是规则的非空有穷集合，用四元组G=(VN,VT,P,S)，其 中VN是规则中非终结符的集合； VT是规则中终结符的集合， VN ∩ VT= ，字汇表V= VN∪ VT, P是规则的集合； S是一 个非终结符，称为文法的开始符号或识别符号，他至少要 在一条规则中作为规则左部出现。
A → 1 A → 2
7）空集 ：不含元素的集合称为空集 ≠ { } ； A=A =
8）符号串的幂 定义：设x是字母表上的符号串，则x的幂运算为： x0=， x1=x， x2=xx， … … ，xn=xn-1x(=x xn-1)
9）符号串集合的幂：（集合的相乘） 定义：若A为符号串集合，则符号串集合的幂为： A0= { } ， A1=A ，A2=AA，… … ， An-1=An-2A， An=An-1A（=AAn-1）， 例：若A={a，b} 则 A1=A={a，b}；
1.规则：又称产生式，它是一个符号与一个符号串的有序对
（A， ），通常写为A → 或A ::=
规则的作用：规定了一个语言的组成与结构（一个语言的语 法规则）。
规则中出现的符号:
非终结符：出现在规则左部能派生出符号或符号串的那些符 号。通常用大写字母表示。
终结符：不属于非终结符的那些符号，是组成语言的基本符 号，通常用小写字母表示。
••••••
A → n
A → 1|2| ••••••|n每个n称为候选式
约定：第一条规则的左部为识别符号；对文பைடு நூலகம்G可只将规则 写出。
例：设字母表={a，b}，试设计一个文法，描述语言 L={a2n，b2n|n ≥1}。
G=(VN,VT,P,S) 其中VN={A,B,D}, VT={a,b},S=A,
任何符号与空串的连结的结果仍为原来的符号串
x=abbc,y=abbbcc 则 xy=abbcabbbcc ; x = x=x
4）符号串的逆
定义：把一个符号串x的所有符号进行倒置，所产生的
新串
~
x
，就为原符号串的逆 。
~
若x=abbc，则 x的逆为：x cbba
5）符号串前缀、后缀和子串
定义：设x是一个符号串，我们把从x的尾部（前部）删 去若干个（包括0个）符号之后所余下的部分称为x的前 缀（后缀）；从一个符号串后删去一个前缀和一个后缀 之后所余下的部分称为符号串的子串。
