0型文法
- 设G=(VN,VT,P,S)是一个文法,如果它的每个产生式α→β是这样一种结构:α∈(VN ∪ VT)*且至少含有一个非终结符,而β∈(VN ∪ VT)*,则G是一个 0型文法
- 又称短语文法,0型文法的能力相当于图灵机(Turing machine);任何0型语言都是递归可枚举的;反之,递归可枚举集必定是一个0型语言
1型或上下文有关的(context-sensitive)
- 设G=(VN,VT,P,S)是一个文法,若P中的每一个产生式 α→β均满足 |β|≥|α|,仅仅 S→ε 除外,则文法G是 1型或上下文有关的
- 在有些定义中,将上下文有关文法的产生式的形式描述为 α1Aα2 → α1βα2 ,其中α1、α2 和 β 都在(VN ∪ VT)* β≠ε,A在VN
- 更能体现 "上下文有关",因为只有A出现在 α1 和 α2 的上下文中,才允许用β取代A
2型或上下文无关的(context-free)
- 设G=(VN,VT,P,S)是一个文法,若P中的每一个产生式 α→β均满足 α是一个终结符,β∈(VN ∪ VT)*,则文法G是 2型或上下文无关的
- 有时将2型文法的产生式表示为 A→β的形式,其中A∈VN,即用β取代非终结符A时,与A所在的上下文无关,所以取名为上下文无关
例题2.4 G=({S,A,B},{a,b},P,S),其中P由下列产生式组成:
- S→aB
- A→aAA
- S→bA
- B→b
- A→a
- B→bS
- A→aS
- B→aBB
可以把相同左部的产生式,缩写为 A→α1 | α2 | ... | αn , 这个元符号 | 读做 "或"
例题2.4的 P可以写为
- S→aB | bA
- A → a | aS | bAA
- B → b | bS | aBB
3型文法 或 正规文法
设G=(VN,VT,P,S),若P中的每一个产生式的形式都是 A→aB 或 A→a,其中 A 和 B 都是非终结符,a∈V*T,则G是3型文法或正规文法
例2.5 文法G=({S,A,B},{0,1},P,S),其中P由下列产生式组成:
- S→0A
- S→1B
- S→0
- S→0
- A→0A
- A→1B
- B→1B
- B→1
- B→0
G是正规文法