例1：文法G: S aSb | ab
L(G)={anbn|n≥1}
28
2.2.2 文法的分类
3型文法（又称线性文法、正则文法、正 规文法）
➢ 如果对文法G中的任一产生式均限制为形如： AB 或 A
其中： A，B∈VN , ∈VT 则称文法G为3型文 法。 ➢ 上述形式的3型文法也称为右线性文法。 ➢ 如果对文法G中的任一产生式均限制为形如：
Ａ0 ＝ { } Ａ1 ＝ { a,b } Ａ2 ＝ AA ＝{ aa,ab,ba,bb } Ａ3 ＝ A2A ＝{ aaa,aab,aba,abb,baa,bab,bba,bbb }
……
Ａn ＝Ａn-1A ＝ AAA……A
12
2.1 基本概念
10.符号串集合的正闭包
设A为符号串的集合，则称Ａ＋为符号串集Ａ的 正闭包．具体定义如下：
文法
字符串集合
16
2.2 .1 文法的定义
2.2.1 文法（Grammar）的定义 文法的定义
一个文法G是一个四元组: G = ( VN, VT, S, P )
其中：
➢ VT (Terminal Vocabulary)是一个非空的有限集合，
它的每个元素称为终极符号或终极符，一般用小 写字母表示。 从语法分析的角度看，终极符号是 一个语言不可再分的基本符号。
可合并为一个，缩写为:
P 1 | 2 | … | n
其中，每个i 称为 P 的一个候选式，符号“|” 读作“或” 。
21
⑥一个文法的核心是产生式。 一般约定:
用< >括起来或 大写字母：非终结符 不用< >括起来或小写字母：终结符
22
例1
G =（VN,VT, S, P） 其中：VN={ S , A}
