形式语言 | Codeboy's Blog

形式陈述

固定字母表 $\Sigma$ 。由 $\Sigma$ 上所有有限字组成的集合记为 $\Sigma^*$ ；一个形式语言就是它的任意子集

L\subseteq\Sigma^*.

语言的元素是字，语言本身可以有限、可数无限，甚至没有任何有限描述。空语言 $\varnothing$ 不含字；语言 $\{\varepsilon\}$ 恰含空字；全集语言 $\Sigma^*$ 接受每个有限字。这三个对象在连接、接受与生成中扮演完全不同的角色。

机器 $M$ 的语言通常写作 $L(M)$ ，表示被 $M$ 接受的全部输入；文法 $G$ 的语言写作 $L(G)$ ，表示它能够生成的全部终结符字。两种记号都把描述器映到一个集合。不同的机器、文法或表达式可以定义同一个 $L$ ，所以“语言相等”比较的是成员，而不是描述文本或运行步骤。

判定问题也可编码成语言。若实例 $x$ 有无歧义且可有效解析的编码 $\langle x\rangle\in\Sigma^*$ ，就把答案为“是”的实例收集为

L_P=\{\langle x\rangle:P(x)\text{ 成立}\}.

机器决定 $L_P$ ，是指它对每个输入都停机并正确回答成员资格；机器识别或半决定 $L_P$ ，只保证对成员最终接受，对非成员则可以拒绝或永不停止。这一区分在有限自动机上看不出来，却是进入可计算性理论后必须保留的接口。

直觉

形式语言把“哪些输入合格”从“怎样判断合格”中分离出来。语言像一份可能无限的规范：它只回答某个字是否属于集合。自动机是逐符号检查规范的机器，文法是产生合格字的规则，正则表达式则是用代数构造压缩描述；三者是观察同一集合的不同坐标系。

这种抽象暂时丢开符号的现实含义，却没有丢开结构。顺序、重复、长度与切分仍然存在，因此“偶数个故障事件”“标识符后跟参数列表”“图编码中存在哈密顿回路”都能成为语言。一个语言属于哪一类，取决于识别成员资格需要多少记忆或计算资源，而不取决于例子来自文本、协议还是组合对象。

编码不是无关紧要的装饰。可计算性层面通常只要求不同合理编码之间可有效互译；复杂度层面还要控制长度膨胀，否则把一个 $n$ 位实例故意展开成指数长编码，会伪造运行时间的改善。语言模型统一了问题，却不会替使用者证明编码合理。

例子与边界

语言

L_{\mathrm{parity}}=\{w\in\{0,1\}^*:w\text{ 中 }1\text{ 的个数为偶数}\}

只要求记住一个奇偶位，因此是正则语言。相比之下， $L_{\mathrm{match}}=\{a^nb^n:n\ge0\}$ 要求把前半段数量带到后半段精确核对；它能由上下文无关文法生成，却不能由有限状态自动机识别。两个例子表面上都在“计数”，真正的分界是所需摘要能否压进固定有限种状态。

协议也可以直接给出语言。设字母表包含 open、data、close，那么“恰好打开一次、传输若干次、最后关闭”的成功会话构成

\{\texttt{open}\,\texttt{data}^k\,\texttt{close}:k\ge0\}.

这个集合只描述完整事件字是否合规，不负责说明事件之间经过多少真实时间，也不包含并发调度。若要加入时间戳、概率或无限运行，就必须换用承载这些结构的模型。

形式语言不是自然语言，也不自动携带语义。某个语言可以收集“语法正确的程序”，但程序是否终止、类型是否安全，是在另一个判定条件下形成的新语言。文法是否歧义又是描述器的性质：同一个无歧义语言可能被一份歧义文法和一份无歧义文法同时生成。

对本库约定的任一非空有限字母表， $\Sigma^*$ 都是可数无限集，而它的幂集不可数；程序、有限自动机和有限文法的描述却都只有可数多个。因此绝大多数形式语言既没有有限语法，也不能被任何程序识别。定义允许它们存在，计算模型只覆盖其中有有效描述的一小部分。

推论与应用

语言运算把已有语言通过布尔组合、连接、重复和编码变换组成新语言。有限状态自动机、下推自动机与图灵机则按可用记忆逐层扩大可识别范围；比较模型表达能力时，真正比较的是它们各自能产生哪些 $L(M)$ 。

语言视角还让归约成为统一方法：把一个问题的实例有效变换成另一个语言的字，并证明成员资格前后等价，就能传递可判定性与复杂度结论。词法分析、语法解析、模型检查和复杂度理论看似任务不同，都依赖这条“对象编码—语言成员—识别资源”的主线。

参考资料

Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013, §0.2.
John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006, Chapter 1.