• 形式语言自动机课程笔记
• 学到编译原理的时候用到了文法相关概念，复习自动机正好把以前的笔记整理一下也贴上来

---

一、问题的提出

• 语言是给定字母表上字符串的一个集合
• 任何有意义的语言，都是符合某些规则要求的字符串的集合
• 我们把这种有意义的语言称作文法
  1. 文法可以用自然语言描述，如英语语法
  2. 文法也可以用严格的规则形式描述，比如C语言文法，这种文法称为形式文法

二、形式文法和形式语言

（1）形式文法

1. 文法：用有限个规则描述无穷多字符串的集合

2. 形式文法（G）：一个文法G是一个四元组 G = ( V, T, P, S )，其中：

   1. V：是变元的有限集。
   2. T：是终结符的有限集。
   3. P：是产生式的有限集，其中每个产生式都是α→β的形式
      • 其中$α∈(V∪T)^+$α∈(V∪T)+，且其中至少有一个V中的符号；$β∈(V∪T)^*$β∈(V∪T)∗。
   4. S：称为文法G的开始符号，决定这组规则最终要定义什么，S∈V。

   示例：

   1. $G_1 = (\{A, B\}, \{0,1\},\{A→0B, B→1B, B→0\}, A)$G1​=({A,B},{0,1},{A→0B,B→1B,B→0},A)
   2. $G2 =( \{A,B,C\},\{a,b\},\{A→aBC, B→b, C→CC, C→ε\}, A)$G2=({A,B,C},{a,b},{A→aBC,B→b,C→CC,C→ε},A)

3. 文法表示方式的约定：

符号	表示
变元	大写字母ABCD…除非特殊说明，否者S表示开始符号
终结符号	小写字母abcde/数字123…
终结符串	小写字母uvwxyz
变元和终结符混合串	希腊字母αβγ…

• 若有若干产生式左部一致，记为$α\to β_1|β_2|..|β_n$α→β1​∣β2​∣..∣βn​

• 上述约定下，写一个文法只需写出产生式集合

  示例：

  1. $G=(\{S\},\{a,b\},\{S→aSb,S→ab\},S)$G=({S},{a,b},{S→aSb,S→ab},S)
     可以表示为：S→aSb|ab

  2. 给出文法G，它的产生式是：

     • S→aB∣bA
     • A→a∣bAA∣aS
     • B→b∣aBB∣bS

     则Ｌ(G)是由相等个数a和b组成的（次序不限）所有串的集合 (可以用归纳法证明)

4. 字符串/文法推倒与规约
   
   4. 最左（右）推倒：对于推导α→β，如果每一步都是对α中的最左非终结符进行替换的，则我们称这种推导为最左推导，如果每一步都是对α中的最右非终结符进行替换的，则我们称这种替换为最右推导， 例如：
      

（2）形式语言

1. 形式语言：给出文法 G=(V,T,P,S)，它所产生的语言记作L(G)，由下述集合定义：
   $L(G)=\{ｗ|S\stackrel{*}{\Longrightarrow} ｗ，并且ｗ∈Ｔ^* \}$L(G)={ｗ∣S⟹∗​ｗ，并且ｗ∈Ｔ∗}
   L(G)是由G中开始符号S推导出来的全体终结符号串所构成的集合，也就是所有句子的集合。

三、文法等价

1. 文法等价：对于两个不同的文法$G_1＝(V_1,T_1,P_1,S_1），G_2＝(V_2,T_2,P_2,S_2)，$G1​＝(V1​,T1​,P1​,S1​），G2​＝(V2​,T2​,P2​,S2​)，如果$Ｌ(G_1)＝Ｌ(G_2)$Ｌ(G1​)＝Ｌ(G2​)，则称文法$G_1$G1​与$G_2$G2​等价。
2. 在两个四元组的各对应部分中，只要有一点点不同，就应当看作是不同的文法，在这个意义下，任何一个语言都可以有无穷多个文法（都等价）产生它。

四、文法的乔姆斯基分类

对于文法　G＝（V，T，P，S）按以下方法分为四类：

1. 0型文法，或短语结构文法（PSG）：
   1. 产生式不加另外的限制。
   2. 产生短语结构语言（PSL）
2. 1型文法，或上下文有关文法（CSG）：
   1. 产生式α→β都满足 |α|≤∣β|
   2. 产生上下文有关语言（CSL）
3. 2型文法，或上下文无关文法（CFG）：
   1. Ｐ中每个产生式都具有如下形式：A→β，β∈(V∪T)*，A∈V
   2. 产生上下文无关语言（CFL）
4. 3型文法，或正则文法（RG）：
   1. Ｐ中每个产生式都具有如下形式：A→a或A→aB，a∈T∪{ε}，AB∈V
   2. 产生正则语言（RL）

五、左/右线性文法