【13.9.1】自动机与形式语言的文法
一. 语言的描述
乔姆斯基将语言定义为：“按照一定规律构成的句子和符号串的有限或无限集合。”
我国计算语言学家吴蔚天也给出了自己对语言的定义：“语言可以被看成一个抽象的数学系统。”
无论把语言看作集合还是数学系统，我们都可以用数学的方法来进行刻画和描述，那么一般地，描述一种语言可以有三种途径：
穷举法：把语言中的所有句子都枚举出来。显然，这种方法只适合句子数目有限的语言。（这种方法显然不太靠谱啊，我们所使用的语言实在是太多了）
文法(产生式系统)：语言中的每个句子用严格定义的规则来构造，利用规则生成语言中合法的句子。（就是形式语言）
自动机法：通过对输入的句子进行合法性检验，区别哪些是语言中的句子，哪些不是语言中的句子。（自动机是和形式语言配合其作用的，每一种形式语言对应着一个自动机）
二. 形式语言
形式语言是用来精确地描述语言(包括人工语言和自然语言)及其结构的手段。形式语言学也称代数语言学。
1. 形式语法(文法)
𝐺=(𝑁,𝑇，𝑃，𝑆)
通俗的说,终结符号就是语言中用到的基本元素,一般不能再被分解:名词,动词,形容词,助词,等等基本语言单位.
-
N：非终结符，不能处于生成过程的终点，即在实际句子中不出现。在推导中起变量作用，相当于语言中的语法范畴；比如,主语,短语,词组,句子。
-
T：终结符的有限集合，只处于生成过程的终点，是句子中实际出现的符号，相当于单词表。
-
P：重写规则、生成规则的有限集合.
-
S：N中的初始符号，相当于语法范畴中的句子。
文法𝐺的不含非终结符的句子形式称为𝐺生成的句子； 由文法 𝐺 生成的语言，记做 𝐿(𝐺)，指𝐺生成的所有句子的集合。
2. 形式语法的类型——根据重写规则P
-
正则文法 3型文法
-
正则文法规则右边有约束：左/右线性正则文法
-
上下文无关文法 2型文法
-
上下文无关和正则文法规则左边只有一个非终结符；下面两个文法可以有多个，涉及“上下文内容”
-
上下文有关文法 1型文法
-
无约束文法 0型文法
从0型文法到3型文法，对规则的约束越来越多，每一个正则文法都是上下文无关文法，每一个上下无关文法 都是上下文有关文法，而每一个上下文有关文法都可以认为是0型文 法。因此，从0型文法到3型文法所识别的语言集合越来越小。
我们约定，如果一个文法的产生式集合P中，有分属于不同类型文 法的产生式，则把属于包含最广类型文法的那条产生式所属的类型作为 这个文法的类型。比如说，某个文法的全部规则分别属于1型文法、2型 文法和3型文法，则我们称这个文法为1型文法。同理，如果一种语言能够由几种文法所产生，则把这种语言称为在这几种文法中受限制最多的那种文法所产生的语言。
3.其他
通过文法可以规范化的表达某种语言（语言就是串的集合），我们通过四元组来表示一个文法：
G = ( V , T , P , S )
其中
-
V 是 variable，表示变量，即状态的集合。
-
T 是 terminal，终极符，通过一系列的终极符号 T，在不同的变量（V）中进行跳转。比如 V1 可以通过接收字符 T，从而转到 V2 状态。
-
S 是 start symbol，为文法的开始符号，其中 S 属于状态集合 V
-
P 为 production，即产生式。产生式告诉我们状态之间的联系，比如一个状态 V 可以产生一个字符 0，那么有：
V→0
当然也可以递归地进行产生，比如产生的结果中，包含自己：
V→0V
一个规范化的四元组长这样：
G=({A,B}, {0,1}, {A→0,A→1A,B→0A,B→1}, B)
通过产生式，推出一个字符串产生的过程，叫做推导。例子如下，给出文法 G，写出句子 aaa 的推导过程
G=({A}, {a}, {A→a∣aA}, A)
推导的过程如下：
A→aA, 使用产生式A→aA
aA→aaA, 使用产生式A→aA
aaA→aaa, 使用产生式A→a
归约则是和推导（又称为派生）相反的过程，通过句子推导出文法。
三. 自动机
自动机可分为有限自动机(有限状态机)、下推自动机、线性界限自动机、图灵机。
各类自动机之间的主要区别是它们能够使用的信息存储空间的差异:
- 有限状态自动机只能用状态来存储信息;
- 下推自动机除了使用状态以外，还可以用下推存储器(堆栈);
- 线性界限自动机可以利 用状态和输入/输出带本身，因为输入/输出带没有“先进后出”的限 制，因此，其功能大于堆栈;
- 而图灵机的存储空间没有任何限制。
从识别语言的能力上来看，有限自动机等价于正则文法;下推自动机等价于上下文无关文法;线性界限自动机等价于上下文有关文法，而图灵机等价于无约束文法。
参考资料
