语言与自动机

引入

同我们的日常交流一样，计算机的计算实际上是数据的交流，这一过程依赖于算法。算法对数据处理的规范称为语言。每个算法只能处理符合自己规范的数据，就如同你只能用汉语理解“你好”一样。我们把符合算法规范的数据称为这个语言（L）的句子。

乔姆斯基最初从产生语言的角度研究语言，因此 $L \subseteq \Sigma^\star$。

现在，我们考察一个字符串是否是某个语言的句子。这里我们引入无穷语言的有穷描述———文法。文法是语言的规范化描述，我们可以通过判断一个字符串是否符合文法确定这个字符串是否是语言的句子。

文法

文法 $G$ 是一个四元组：$G =(V,T,P,S)$

• $V$：变量的非空有穷集合。$\forall A \in V$，$A$ 称为语法变量或非终极符号。
• $T$：终极符的非空有穷集合。$\forall a \in T$，$a$ 称为终极符。要求 $V \cap T = \emptyset$。
• $P$：产生式的非空有穷集合。产生式均具有形式 $\alpha \to \beta$，读作 $\alpha$ 定义为 $\beta$。
  要求 $\alpha \in (V \cup T)^+$，即 $\alpha$ 不能是空字符串。且 $\alpha$ 中至少有 $V$ 中的一个元素出现。
  要求 $\beta \in (V \cup T)^\star$， $\beta$ 可以是空串 $\varepsilon$。
  $P$ 定义了非终极符号之间的转换规则。
• $S$：开始符号，$S \in V$。

文法的乔姆斯基体系

正则语法 $\subset$ 上下文无关文法 $\subset$ 上下文有关文法 $\subset$ 短语结构文法