语言、文法

语言

语言的定义和运算这里简要省略，可以直接看书复习
只用注意一下，语言的乘积运算是不可交换的

文法

Chomsky文法体系

形式定义： 文法
其中，N是非终结符的有限集合
T是终结符的有限集合
P是生成式的有限集合
S是起始符，
P的形式为 ，其中必须含有至少一个非终结符号（目的是为了保障至少能化简，不然没意义

推导与生成式的区别：推导是句子中含有生成式的成分，然后从而推导出另一个句子
句型和句子：句型指没有推导到最后的结果，即其中含有非终结符
句子中只有终结符
由文法产生的语言，记作L(G)，必须是由终结符组成，从起始符S推导出的

文法的分类

0型文法：即上述形式定义，不加以任何限制，对应无限制语言，
1型文法：上下文有关文法，生成式的形式为，其中，，且，重点是左侧的长度一定要小于右侧，对应上下文有关语言
2型文法：即上下文无关文法，生成式的形式为，其中，且
生成式的左部分只能是单个非终结符！对应上下文无关语言
3型文法：即正则文法，生成式的形式为 ， ，对应正则语言
重点是，它的形式必须为先终结符后非终结符的形式。