形式语言与自动机学习笔记(1)：文法与自动机概述

一、概述

• 形式语言：形式化描述的字母表上的字符串构成的集合；
• 自动机：具有离散输入输出的数学模型；

形式语言与自动机的关系：
形式语言——字符串，自动机——字符串的识别系统

• 文法：定义语言的数学模型；
• 元语言：描述语言的语言；

二、Chomsky文法体系

概念简述

文法$G$是一个四元组$G=(N，T，P，S)$，其中：

• $N$：非终结符的有限集合；
• $T$：终结符的有限集合，且$N\cap T = \phi$；
• $P$：形式为$\alpha \rightarrow \beta$的生成式的有限集合，且$\alpha \in (N \cup T)^* N^+ (N \cup T), \beta \in(N\cup T)^*$，即$\alpha$中至少含有一个非终结符；
• $S$：起始符，且$S\in N$；

应用生成式就是将非终结符不断替换为终结符+非终结符的符号串，再替换得到的新的字符串中的非终结符，最终得到只含有终结符的符号串；
我们将中间过程的符号串称为句型，最终推导出的只含有终结符的符号串称为句子，显然，句型包含句子。

我们将文法产生的语言记为$L(G)$：

$$L(G) = \{ \omega \mid \omega \in T^* \text{ 且 } S \Rightarrow^* \omega \}$$

即必须是由终结符组成，并且由起始串$S$推导得到；

关于Chomsky文法体系，对生成式做出一些限制，分为以下4类：

0型文法

• 无限制
• 对应递归可枚举语言
• 对应图灵机

1型文法

• 上下文有关文法
• 对应上下文有关语言
• 对应线性有界自动机（不考虑空串）

1型文法对生成式做出了如下限制：$\alpha \rightarrow \beta$，其中$|\alpha| \leq |\beta|$，且$\alpha, \beta \in (N \cup T)^*$，且$\alpha$至少含有一个非终结符号；
该限制的意义是保证了推到过程中字符串长度单调不减；

2型文法

• 上下文无关文法
• 对应上下文无关语言
• 对应下推自动机

2型文法对生成式做出了如下限制：$A \rightarrow \alpha$，其中$A$是一个非终结符，$\alpha$是由非终结符和终结符组成的任意字符串（可以是空串）；
该限制的意义是每次替换单独一个非终结符，支持递归结构的解析；

3型文法

• 正则文法（分为左线性文法和右线性文法）
• 对应正则语言
• 对应优先自动机

左线性文法对生成式做出了如下限制：$A \rightarrow B\omega$或$A \rightarrow \omega$，其中$A,B$为非终结符，$\omega$为终结符；
右线性文法对生成式做出了如下限制：$A \rightarrow \omega B$或$A \rightarrow \omega$，其中$A,B$为非终结符，$\omega$为终结符；
该限制的意义是，生成式只能在字符串的左边或者右边扩展非终结符，限制了语言的复杂性和递归性；