一、概述

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

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

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

二、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\)为终结符；
该限制的意义是，生成式只能在字符串的左边或者右边扩展非终结符，限制了语言的复杂性和递归性；

有限自动机

DFA

DFA是一个五元组\(M = (Q,T,\delta. q_0, F)\)；
* \(Q\)：有限状态集合；
* \(T\)：有限的输入字母表；
* \(\delta\)：转移函数：\(Q \times T \rightarrow Q\)；
* \(q_0\)：起始状态；
* \(F\)：终止状态的集合；

\(\delta'\)函数：接受一个字符串输入的状态转移函数：
\[ \delta':Q\times T^* \rightarrow Q \]
对任何\(q \in Q\)，作出如下定义：
* \(\delta'(q, \varepsilon) = q\)；
* 若\(\omega\)为字符串，\(a\)为一个字符，则\(\delta'(q, a\omega) = \delta(\delta'(q, \omega), a)\)；

被DFA接受的字符串：输入结束后使DFA达到终止状态；

格局：当前状态\(q\)，待输入字符串\(\omega\)，用\((q, \omega)\)表示当前瞬时状态；

UFA 不确定的有限自动机

在某个状态，对应某个输入，有多个转移，能到达多个状态；UFA和DFA的定义上的区别只有\(\delta\)函数：
\[ \delta：Q\times T\rightarrow 2^Q \]
如果接受一个字符串后UFA能够到达的状态集合包含一个及以上F中的元素，则称为该字符串能被UFA接受；