语言：语言可以看成在一个基本符号集上定义的，按一定规则构成的基本符号串组成的所有
集合。语言研究的三个方面 语法（Syntax）： 表示构成语言句子的各个记号之间的组合规律，有词法规则和语法规则语义（Semantics）：表示按照各种表示方法所表示的各个记号的特定含义
语用（Pragmatics）：表示在各个记号所出现的行为中，它们的来源、使用和影响1 字母表
是符号的非空有穷集合用 ∑ 表示2 符号(字符)字母表中的元素称为符号是语言中最基本的不可再分的单位符串是字母表中符号组成的有穷序列空串:不含有任何符号的串称为空串，记作 ε 4 句子 字母表上符合某种规则构成的符号串5 语言 字母表上句子的集合1 符号串连接 连接符号串x、y，把y的符号串写在x的符号串之后得到的符号串;即x、y的连接为xy。注意，一般xy yx。符号串集合：若集合中所有元素都是某字母表上的符号串，则称之为该字母表上的符号串集合。2 集合的乘积：
AB={ x y | x A , y B } 满足条件的所有xy的集合。
例：符号串集合A＝{ab,aa},B={ba,bb}
乘积AB＝{abba,abbb,aaba,aabb}
注：{ε}A=A{ε}=A
3 符号串的幂运算
符号串自身连接n次得到的符号串
如：x的n次连接为xx…..x（n个x），也可
记作X^n
注：x0＝ε
4 集合的幂运算
集合A连接自身n次所得到的集合
假设A={a,b}
A0={ }
A1=A＝{a,b}
A2=AA＝{aa,bb,ab,ba}
A3=AAA＝{aaa,aab,…}
2.3.1 语言(language)：某个字母表 ∑ 上的符号串的集合，是 的一个子集。
描述语言的方法：
（a）如果语言是有穷的，可以将句子逐一列出来表示。（枚举）
（b）如果语言是无穷的，找出语言的有穷表示。（文法）
例1 设L1={a2n,b2n|n>=1}，试构造出生成L1的文
法G1。分析 L={aa,bb,aaaa,bbbb,aaaaaa,bbbbbb,…}是由偶数个a,偶数个b组成的集合。
G1[S]:
S aa|aaA|bb|bbB
A aa|aaA
B bb|bbB
G2[S]:
S A|B
A aa|aAa
B bb|bBb
例2 设L2={abna|n>=0}，构造出生成L2的
语言G2。
G2[S]：S aBa
B Bb|
例3 设L3={ | (a,b)* 且 中含有相同个数的a和b}，试构造出生成L3的文法G3。
G3[S]:
S aA|bB|
A aAA|bS|b
B aS|a|bBB
G3[S]’:
S aSbS|bSaS|ε
例4 设L4={ | (0,1)*且 中1的个数为偶数}，试构造生成L4的文法G4。
G4[S]:
S 0S|1A|ε
A 0A|1S
例 2.10 设有文法G[S]:
S→AB
A→A0 | 1B
B→0 | S1
请给出句子101001的最左和最右推导。
最左推导：
S AB 1BB 10B 10S1 10AB1 101BB1
1B1001 101001
最右推导：
S AB AS1 AAB1 AA01 A1B01
A1001
1B1001 101001
句柄是最左直接短语1 语法树 给定文法G，对于G的任何句型都能构造与之关联的语法树（推导树）。这棵树满足下列4个条件：(1)每个结点都有一个V中的符号作标记(2)根的标记是开始符号S(3)若一结点n至少有一个它自己除外的子孙，并且n有标记A，则A (4)如果结点n有k个直接子孙，分支结点的标记从左到右的次序标记分别为A1,A2,…,Ak,那么
A A1A2,…,Ak一定是P中的一个产生式
1 语法树
子树：某一结点连同所有分支组成的部分
短语：子树的叶子结点形成的符号串
直接短语：单层分支子树所形成的短语
句柄：最左直接短语
若一个文法存在某个句型对应两棵不同的语法树，则称这个文法是二义的。
若一个文法存在某个句型有两个不同的最左（最右）推导，则称这个文法是二义的。
4 文法的限制
文法中不得含 有害规则和多余规则，这种文法称为化简了的文法。
有害规则：形如A A的产生式。会引起文法的二义性
多余规则：指文法中任何句子的推导都不会用到的规则
(1) 文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。 (2) 文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。
例：化简文法G[S]
1文法的类型
通过对产生式施加不同的限制，Chomsky将文法分为四种类型：? 0型文法? 1型文法
? 2型文法? 3型文法
0型文法（短语文法）
对任一产生式 ，都有 且 至少包含一个非终结符，? 0型文法又称为无限制文法? 其所描述的0型语言又称无限制语言
3型文法（正规文法）
例子 G(S)：S 0A|1B|0
A 0A|1B|0S
B 1B|1|0
例 文法G(S)：S aB|bA
A a|aS|bAA
B b|bS|aBB