形式语言
1. 关于语言的定义
人类所特有的用来表达意思、交流思想的工具，是一种特殊的社会现象，由语音、词汇和语法构成一定的系统。
2. 语言描述的三种途径
穷举法— 只适合句子数目有限的语言。
语法描述— 生成语言中合格的句子。
自动机— 对输入的句子进行检验，区别哪些是语言中的句子，哪些不是语言中的句子。
3. 推导的定义
设 是一个文法, 在
上定义关系
(直接派生或推导)如下：
如果 是
中的符号串，且
是
的产生式，
那么 。
如下所示：
4. 最左推导、最右推导和规范推导
约定每步推导中只改写最左边的那个非终结符，这种推导称为“最左推导”。
约定每步推导中只改写最右边的那个非终结符，这种推导称为“最右推导”。
最右推导也称规范推导。
5. 句型与句子
一些特殊类型的符号串为文法 的句子形式(句型)：
(1) 是一个句子形式；
(2) 如果 是一个句子形式，且
是
的产生式，则
也是一个句子形式；
文法 的不含非终结符的句子形式称为
生成的句子。由文法
生成的语言，记作
，指
生成的所有句子的集合。即：
6. 正则文法(3型文法)
如果文法 的
中的规则满足如下形式：
，或
，其中
，
则称该文法为正则文法或称3型文法。(左线性正则文法)
如果，则该文法称为右线性正则文法。
7. 上下文无关文法(context-free grammar, CFG)(2型文法)
如果 中的规则满足如下形式：
，其中
，
，则称该文法为上下文无关文法(CFG) 或称2 型文法。
8. 上下文有关文法(context-sensitive grammar, CSG)(1 型文法)
如果 中的规则满足如下形式:
, 其中
，且
至少包含一个字符，
则称该文法为上下文有关文法(CSG) 或称1 型文法。
另一种定义：
，并且
。
9. 0型文法
只要你能描述出来，都属于这个类型，即0型。
10. 4种文法的区别
4种文法的联系
4种文法判别
1.先来看看3型文法的判断规则
①：左边必须只有一个字符，且必须是非终结符；
②：其右边最多只能有两个字符，要么是一个非终结符+终结符（终结符+非终结符），要么是一个终结符。
③：对于3型文法中的所有产生式，若其右边有两个字符的产生式，这些产生式右边两个字符中终结符和非终结符的相对位置一定要固定，也就是说如果一个产生式右边的两个字符的排列是：终结符＋非终结符，那么所有产生式右边只要有两个字符的，都必须满足终结符+非终结符。反之亦然。
2.再看看2型文法判断规则
①：与3型文法的第一点相同，即：左边必须有且仅有一个非终结符。
②：2型文法所有产生式的右边可以含有若干个终结符和非终结符（只要是有限的就行，没有个数限制）。
3.最后再看看1型文法判断规则
①：1型文法所有产生式左边可以含有一个、两个或两个以上的字符，但其中必须至少有一个非终结符。
②：与2型文法第二点相同，但需要满足|α|≤|β|.
- 0型文法不需要判断了，一般的文法都是0型文法。 O(∩_∩)O
11. 上下文无关文法的二义性
一个文法，如果存在某个句子有不只一棵分析树与之对应，那么称这个文法是二义的。
