形式语言是由某个指定符号表中的符号构成的有限字符串的集合。这个集合可以通过列举其成员、给出生成成员的规则,或指定识别成员的机器来描述。与日常口头或书面的语言不同,形式语言由明确的数学条件定义:一个给定字符串是否属于该语言,有确定的答案,即使不存在能在所有情况下回答这一问题的算法。
形式语言为描述编程语言的语法、逻辑公式的结构、文本中的模式以及计算系统所接受的输入提供了统一框架。对形式语言的研究将计算机科学、数学、语言学和逻辑学联系起来。其核心问题包括:如何表示语言,识别语言需要哪些计算资源,以及语言描述的哪些性质可以通过机械化方法判定。
形式语言理论将语言本身与对它的任何一种具体描述区分开来。不同的文法、表达式或机器可能定义完全相同的字符串集合,而看似相近的描述却可能具有截然不同的计算性质。这一区分既是语言数学分类的基础,也为编程语法设计、语法分析器构造、验证和数据交换中的实际决策提供依据。
字母表、字符串与语言的定义
字母表通常记作 ,是一个有限的符号集合。 上的字符串(也称为字)是由这些符号组成的有限序列。例如,若 ,则 、 和 都是 上的字符串。符号是抽象对象,不一定是印刷字符:字母表可以由二进制数字、标识符和运算符等词法单元,或描述系统中事件的标签组成。
不包含任何符号的字符串是唯一的,称为空串,通常记作 。字符串 的长度记作 ,因此 。所有长度为 的字符串构成的集合记作 ,所有有限字符串构成的集合则为
记号 表示不包含空串的字符串集合。 上的形式语言是任意子集 。因此,空语言 、只含一个元素的语言 、任意有限的字符串集合,以及 本身,都是语言。特别要注意, 与 并不相同:前者不含任何字符串,后者则含有一个长度为零的字符串。
连接是将字符串接在一起的操作,不插入任何额外符号。若 且 ,则 。连接满足结合律,以 为单位元,但一般不满足交换律。在这一运算下, 构成由 生成的自由幺半群。“自由”是指,除了结合律和单位元法则所要求的等式之外,不对符号序列施加任何额外的等式关系。这一代数视角使我们能够通过映射到其他代数结构来研究字符串问题。
对于非空的有限字母表, 是可数无穷集,但它的所有子集构成的集合是不可数的。相比之下,用一套固定的有限记号写出的有限描述只能构成可数集。因此,大多数形式语言都无法用任何有限文法、程序或类似的有限描述来刻画。所以,形式语言理论并不将“语言”等同于“可有效识别的语言”;后者只是一个受限的类别。
所选的表示方式也很重要。源程序可以被视为字符串、词法单元序列,也可以被视为编码后的字节序列。例如,一个 Unicode统一码字符在 UTF-8编码中不一定只对应一个字节。在某一表示层面上确立的性质,并不一定能原封不动地适用于另一层面,不过,明确的编码往往能够在不同层面之间建立精确的转换。
语言的运算与变换
语言可以进行并、交、差、补等集合运算。如果 和 是同一字母表上的语言,那么 包含属于其中任一语言的字符串,而 包含同时属于两种语言的字符串。补集始终是相对于某个给定的字母表而言的: 在 上的补集是 。因此,即使 中列出的字符串保持不变,改变 也可能改变其补集。
连接运算可以从字符串推广到语言:
语言的幂定义为 和 。克莱尼星闭包和正闭包分别为
对于 ,语言 包含 、、、、 和 。这些构造描述的是将 中的完整字符串反复连接,而不是任意重排其中的单个符号。
同态将每个符号替换为一个固定的字符串,并将这种替换扩展到字符串的连接。形式上,映射 满足 和 。如果 且 ,那么 。通过取像,同态将语言变换为 。反过来,逆像 包含所有经变换后属于 的源字符串。同态可以用来描述编码和抽象;当某些符号映射到 时,也可以用来描述对无关符号的删除。
其他有用的运算包括逆序和商:逆序将每个字符串的符号顺序颠倒,商则移除可能的前缀或后缀。对于固定字符串 ,左商为
这是读入 之后所有可能的后续字符串所构成的集合。商将语言运算与识别联系起来:识别器在处理前缀时,需要保留足够的信息,以区分后续可能接续的字符串集合不同的前缀。
如果对某个语言族中的语言施加一种运算,所得语言始终仍属于该语言族,就称该语言族对这种运算封闭。封闭性定理既揭示结构性质,也提供构造方法。例如,正则语言对并、交、补、连接和星闭包运算都封闭。上下文无关语言对并、连接和星闭包运算封闭,但对任意的交运算或补运算不封闭。这些差异有助于证明某种拟采用的表示方式能力不足,也解释了为什么将各自易于处理的规约组合起来后,可能需要更强大的识别器。
文法与生成式描述
形式文法通过重写符号串的规则来规定一种语言。常见的定义是四元组 ,其中, 是非终结符的有限集合, 是由终结符组成且与 不相交的字母表, 是产生式的有限集合, 是开始符号。非终结符表示中间结构;终结符则是最终生成的符号串中保留下来的符号。
产生式 允许将符号串中出现的一处 替换为 。应用一次产生式记作 ,而 表示应用零次或多次产生式。生成的语言为
在无限制文法中,产生式的左部必须至少包含一个非终结符;除此之外,产生式可以替换符号串中的大段内容。对产生式的形式施加更多限制,就会得到一些重要但表达能力较弱的语言族。
上下文无关文法将每条产生式限制为 的形式,其中 是单个非终结符。例如,
生成的语言恰好是 。每次递归应用 都会增加一个 和一个 ,最后再用另一条规则消去剩余的非终结符。推导
展示了有限的规则集如何描述无限的语言。
上下文无关推导可以用具有层次结构的语法分析树来表示。树根是开始符号,内部结点按照产生式展开,叶结点从左到右排列便构成推导出的符号串。这种表示方式记录了分组信息,而这些信息在扁平的终结符串中可能并不显式呈现。例如,算术表达式文法必须区分乘法与加法,并表示括号所规定的分组。这类结构通常用树(数据结构)来实现。
如果某个符号串有不止一棵语法分析树,等价地说,有不止一种最左推导,那么该文法就是二义的。文法 是二义的,因为 可以有不同的分组方式。通过为表达式、项和因子分别引入非终结符,可以确保运算遵循规定的优先级和结合性。不过,二义性是文法的性质,并不必然是其语言的性质:有些二义文法可以替换为定义相同符号串集合的无二义文法。只有当不存在能够生成某种上下文无关语言的无二义上下文无关文法时,才称该语言是固有二义的。这一区别说明,必须将描述本身的性质与它所表示的语言的性质区分开来。
乔姆斯基层级
乔姆斯基层级依据对产生式的限制以及等价的计算模型,对文法和语言进行分类。在标准的有限字符串框架下,它包括正则语言、上下文无关语言、上下文有关语言和递归可枚举语言。这些语言类构成如下严格包含链:
这一层级划分的是表达能力,而不只是执行速度或某种记法表面上的复杂程度。
正则语言可以由始终采用右线性形式的文法生成,其产生式形如 、,也可包含规则所允许的空串产生式。等价地,它可以用经典的正则表达式描述,也可以由有限自动机识别。正则语言能够表达那些只需有限个可区分的记忆状态就能判定的约束,例如含有偶数个 的二进制串,以及以字母开头、后接若干字母或数字的标识符。它们的局限并不在于字符串的最大长度;有限自动机可以识别包含无穷多个字符串的语言。
上下文无关语言可以由上下文无关文法生成,并由非确定性下推自动机识别。额外的栈使其能够处理嵌套深度无界的结构。配对正确的括号串以及语言 都是上下文无关语言,但不是正则语言。上下文无关结构在程序设计语言的语法中占据核心地位,不过,要完整判定程序是否合法,通常还需要满足上下文无关文法无法刻画的其他要求。
上下文有关语言可以使用非收缩产生式生成,即产生式右侧的长度不小于左侧的长度。按照惯例,在对开始符号施加适当限制的条件下,可以允许空串产生式作为例外。这类语言由非确定性线性有界自动机识别;这种自动机是一种图灵机,其可用纸带长度受输入长度的某个常数倍所限制。语言 是上下文有关语言,但不是上下文无关语言。确定性与非确定性线性有界自动机能否识别相同的语言类,至今仍是一个开放问题。
递归可枚举语言也称为可计算枚举语言或图灵可识别语言,由无限制文法生成,并由图灵机识别。识别要求机器对属于该语言的字符串最终接受,但对不属于该语言的字符串,机器可能永远运行下去。可判定语言是指存在某台机器,对任何输入都能停机并给出正确判断的语言;这一语言类严格介于上下文有关语言类与递归可枚举语言类之间。
这一层级并未囊括所有有用的语言分类。确定性上下文无关语言构成上下文无关语言的真子类;而弱上下文有关语言族的提出,则是为了刻画超出上下文无关文法能力的结构,同时又不采用上下文有关语言识别的全部能力。受资源限制的复杂性类以及由代数方法定义的子类,与这一层级交叉分布,用于回答这一层级原本并非旨在解决的问题。
自动机、记忆与识别
识别器读取输入串,并判断它是否属于某种语言。确定性有限状态机具有有限的状态集 、输入字母表 、转移函数 、初始状态 和接受状态集 。读完整个输入后,是否接受取决于当前状态是否属于 。无论输入有多长,它的全部记忆都只有当前状态。
对于包含偶数个 的二进制串,两个状态就足够了:一个表示偶数,另一个表示奇数。读到 时切换状态;读到 时状态不变。表示偶数的状态既是初始状态,也是接受状态,因此空串也会被接受。自动机并不存储 的数量,只保留与后续是否接受有关的信息。
非确定性自动机对于同一状态和同一输入符号,可以有多个可能的下一状态,也可以允许不消耗输入的转移。只要至少有一条计算路径接受某个串,这个串就被接受。非确定性并不会扩大正则语言的范围:子集构造法可以将具有 个状态的这类自动机转换为等价的确定性自动机,后者至多有 个状态。对于某些语言族,这种指数级增长不可避免。因此,表达能力相同,并不意味着表示同样紧凑。
加入一个栈,就得到了下推自动机。栈可以保存任意多个符号,但只允许访问栈顶。为了识别 ,自动机可以在每读到一个 时压入一个标记,然后在每读到一个 时弹出一个标记,只有在数量相等且输入顺序正确时才接受。非确定性下推自动机能够识别所有上下文无关语言;确定性下推自动机所能识别的则是其中的一个真子集。与有限状态的情形不同,下推自动机的确定化无法对所有语言都保持原有的识别能力。
迈希尔–尼罗德定理从可区分前缀的角度解释了有限状态记忆。定义
如果在两个前缀后接上任意相同的后缀,得到的串是否属于该语言的结果都一致,那么这两个前缀就是等价的。一种语言是正则语言,当且仅当这一等价关系只有有限多个等价类。这些等价类与该语言的最小完全确定性自动机的状态一一对应。对于 ,前缀 两两可区分:接上 后, 得到的串会被接受,而当 时, 得到的串不会被接受。因此,识别这种语言需要区分无穷多种情况,有限状态自动机无法做到。
判定问题与计算复杂性
形式语言理论区分针对特定输入的问题与针对整个描述的问题。成员资格问题询问是否有 。空性问题询问是否有 。等价性问题询问两个描述是否定义了同一种语言,而包含性问题则询问是否有 。其他问题涉及有限性、普遍性、文法歧义性,以及是否存在特定的结构模式。这些问题的答案在很大程度上取决于所用的表示方式和语言类别。
对于给定的确定性有限自动机,成员资格判定所需的时间与输入长度成线性关系。空性问题可归约为检查能否从初始状态到达某个接受状态。等价性可以通过检查两个自动机所接受语言的对称差是否为空来判定。状态最小化也有有效算法;最小的完全确定性自动机在不计状态重命名的意义下是唯一的。这些构造性结果使正则语言特别适合用于需要反复组合、比较和优化规约的工具中。
对于上下文无关文法,成员资格仍然是可判定的。对固定文法而言,Cocke–Younger–Kasami 算法采用适当的范式,其标准时间上界为输入长度的三次方。Earley 算法在一般情况下的最坏时间上界也是三次方,而对一些重要子类则有更好的上界。这两种算法都利用动态规划,复用有关子串或部分推导的信息。上下文无关语言的空性和有限性是可判定的,但对于任意上下文无关文法,等价性、包含性、普遍性和歧义性都是不可判定的。因此,单个字符串可能很容易检验,但文法描述之间的全局比较在一般情况下却无法自动完成。
在图灵机层面,必须明确区分可判定性。递归可枚举语言的识别器可以接受属于该语言的输入,但在输入不属于该语言时可能永不停机。判定器则必须对每个输入都停机。一个语言可判定,当且仅当它及其补集都是递归可枚举的:可以交替模拟两个识别器的执行步骤,直到其中一个接受。通过与停机问题建立联系,可以证明:对于任意不受限制的描述,不可能存在判定成员资格或空性的通用方法。
计算复杂性通过衡量时间、空间及其他资源,对可判定性作出更细致的刻画。一个判定问题可以表示为由其所有答案为“是”的实例的编码组成的语言。例如,布尔可满足性问题所对应的语言,由所有存在满足赋值的布尔公式的编码组成。多项式时间归约将一种语言的实例转换为另一种语言的实例,同时保持成员资格不变,因此语言成为NP完全性理论中的基本研究对象。对资源需求的论断必须明确输入的表示方式:给定确定性自动机时判定成员资格,与给定非确定性自动机时判定其语言是否具有普遍性,是不同的问题。紧凑的描述可以缩小表示规模,却将大量计算工作转移到分析阶段。
证明局限性与结构分类
要区分不同的语言类,需要能够证明不可能性的方法,而不能仅仅说明某种具体构造失败了。正则语言的泵引理指出:对于每个正则语言,都存在一个数 ,使得其中每个满足 的字符串 都可以写成 ,其中 、,并且对于每个整数 ,都有 。其中可重复的片段对应于有限自动机接受该字符串时的计算路径上的一个环。
要证明 不是正则语言,可以假设存在这样的泵长度,并选取 。任何符合条件的非空片段 都位于开头由符号 组成的区块内。将它删去后,符号 的数量发生变化,而符号 的数量保持不变,这与引理矛盾。量词的顺序至关重要:证明必须涵盖引理允许的每一种分解,而不能只选取一种便于论证的分解。此外,满足泵引理并不足以证明一个语言是正则语言。
上下文无关语言也有相应的泵引理,其中字符串的两个片段一同重复。利用它可以证明 不是上下文无关语言。奥格登引理等更强的结果允许标记字符串中选定的位置,能够处理基本的泵引理论证不足以解决的情形。闭包性质提供了另一条途径:将一个假定为上下文无关的语言与精心选取的正则语言求交,可能会分离出一个已知不是上下文无关的结构。与正则语言求交会保持上下文无关性,尽管任意两个上下文无关语言的交集未必仍是上下文无关语言。
一种代数方法是为每个字符串赋予一个变换,或一个有限幺半群中的元素。一个语言是正则语言,当且仅当它是某个有限幺半群的某个子集在一个从 出发的同态下的原像。语言的句法幺半群刻画了字符串置于任意左右上下文中时,与其是否属于该语言有关的区别。这不同于迈希尔–尼罗德定理直接采用的右上下文等价关系,但两者都能为正则语言给出典范的有限结构。
代数可以识别出具有精确逻辑刻画的子类。无星语言是仅使用有限语言、布尔运算和连接运算,而不使用克莱尼星运算就能表达的语言。它们恰好是句法幺半群为非周期幺半群的正则语言,也恰好是以单词位置为论域、使用顺序谓词和符号谓词的一阶逻辑所能定义的语言。一个更广泛的对应关系表明,正则语言恰好是有限单词上的单元二阶逻辑所能定义的语言。这些结果解释了为什么自动机、公式和代数描述能够以截然不同的形式表达相同的限制。
编程语言、语法分析与数据格式
编译器通常会分几个与语言相关的层次处理源文件。词法分析将字符组合成标识符、数值字面量、标点符号和关键字等词法单元。句法分析,也称语法分析,判断所得的词法单元序列是否符合某个文法,并构建结构化表示。后续阶段则负责名称解析、类型检查以及赋予程序语义。这些阶段之间的界限取决于工程设计,但区分词法模式、文法结构和语义约束仍然很有用。
正则表达式和有限自动机常用于描述词法单元的类别。嵌套结构通常由上下文无关语法分析技术处理。LL 分析器根据接下来的词法单元预测应采用的产生式,而 LR 分析器则识别何时应将已经读入的序列归约为某个文法符号。唐纳德·克努特于 1965 年提出了 LR 分析。语法分析器生成器可将适当的文法描述转换为可执行的分析器,但文法设计必须考虑优先级、结合性、错误处理,以及所选分析方法施加的限制。
仅靠上下文无关文法,通常无法刻画所有合法程序。声明可能必须先于使用,标识符可能必须在特定作用域内可见,某项运算也可能要求操作数具有兼容的类型。这类约束通常通过符号表和类型系统来检查。有些语言的语法分析还依赖分析过程中获得的信息;在C编程语言中,标识符是否为 typedef 名称,会影响后续词法单元的解释方式。因此,编译器实际接受的语言,并不总能仅用一个独立的上下文无关语法分析阶段来理解。
数据格式同样结合了多个层次。JSON具有递归的数组和对象结构,而成员名称、允许的值或应用特有的关系,则可能受到额外约束。XML将良构性与依据文档文法或模式进行的有效性验证区分开来。将结束标签与相应的开始标签匹配,需要建立名称之间的关系;仅仅在基于字符串的基本上下文无关文法中加入配对定界符,并不能刻画这种关系。文法识别、结构验证和应用层解释仍是不同的任务。
精确区分这些概念,对网络安全同样重要。由于转义规则、字符解码方式或消息边界不一致,两个组件可能以不同方式处理同一组字节。如果将数据嵌入命令语言时未能保持其预期的文法角色,就可能产生注入漏洞。实际使用的正则表达式库还带来了另一层复杂性:反向引用可以指定超出正则语言范围的模式,而某些采用回溯的实现,在处理特定输入时可能需要指数级时间。因此,有限自动机的数学保证,并不会自动适用于所有被称为“正则表达式”的功能。形式语言模型有助于厘清:哪些保证源于规范,哪些则取决于实现。
语法、语义与更广泛的语言模型
形式语言作为字符串的集合,本身并不赋予其成员任何意义。语法决定哪些表达式是合式的;语义则赋予表达式相应的解释或行为。同一种语法语言可以有多种解释。例如,算术表达式可以在整数、实数、固定位宽的机器数值或符号对象上解释,而这些解释在溢出、除法和代数恒等式方面会产生不同的结果。反过来,不同的语法记法也可能表示相同的数学对象或计算。
形式系统在形式语言的基础上加入了公理、推理规则等机制。在证明助手中,表达式和证明必须同时满足语法要求与逻辑要求。合式公式的集合、可推导公式的集合,以及在某个选定解释下为真的公式集合,是不同的语言或表达式集合。对于一阶逻辑,标准的有效证明系统允许枚举所有有效公式,但一阶有效性是不可判定的。因此,精确的语法使推理能够由机械方式处理,却并不使每个语义问题都变得可判定。
通常的定义使用有限字符串,但相关理论也研究无限字。ω-语言是 的一个子集,后者是所有无限符号序列的集合。由于无限输入没有最后一个位置,是否接受就不能取决于读完整个输入之后的最终状态。Büchi 自动机采用另一种接受条件:只要存在一条运行路径,无限多次到达接受状态,就接受该输入。这类模型可以表示系统持续运行时的行为,包括有关请求反复出现或最终得到响应的性质。它们将形式语言与形式验证和时序逻辑联系起来;在这些领域中,需求描述的是事件如何随时间演变。
另一些扩展则改变所识别对象的形态,或为这些对象赋予权重。树语言直接描述层次结构,而不是描述其线性编码;它们适用于程序语法和结构化文档。加权自动机通过组合计算过程中的权重,为字符串赋予相应的值。根据所采用的底层代数结构,这些值可以表示代价、计数或概率。概率文法为产生式的选择引入概率分布,但一个规则系统生成字符串的能力,与它对概率质量的分配,是两个独立的数学性质。
形式语言方法也为自然语言处理提供了思路,不过,不能简单地将人类语言等同于一个毫无争议的合乎语法的字符串集合。语法判断取决于语境、意义、方言和用法。上下文无关文法和温和上下文相关文法提供显式的结构模型,而统计语言模型则为词元序列赋予概率。字符串上的概率分布与判断字符串是否合乎语法的成员资格判据并不是同一种对象:为一个字符串赋予非零概率,并不能证明它合乎语法。结构约束与概率建模之间的相互作用,既涉及系统允许哪些序列,也涉及系统对这些序列的偏好程度。
历史发展与研究方向
形式语言理论源自多种学术传统,而非某一项单独的发明。19 世纪至 20 世纪初,数理逻辑发展出各种符号系统,明确规定了构造表达式和进行证明的规则。20 世纪 30 年代关于可计算性的研究,使有效的符号操作过程成为数学研究的对象。艾伦·图灵于 1936 年提出的机器模型,为符号序列上的计算提供了通用描述,后来又与语言的识别和生成联系起来。
有限状态方法在逻辑、开关理论和通信研究中逐步发展。沃伦·麦卡洛克和沃尔特·皮茨于 1943 年开展的理想化神经元网络研究,推动了对有限状态行为的探索。斯蒂芬·克莱尼于 1956 年发表的研究确立了正则表达式与有限自动机之间的对应关系。迈克尔·拉宾和达纳·斯科特 1959 年的研究中所涉及的子集构造法,阐明了确定性有限自动机与非确定性有限自动机的等价性。这些成果使人们能够在类似模式的描述与类似机器的描述之间进行系统转换。
诺姆·乔姆斯基在 20 世纪 50 年代发表的一系列论文,包括他在 1956 年和 1959 年关于文法模型的研究,确立了如今称为乔姆斯基层级的分类体系。这些研究最初直接关注的是语言结构,但这一层级也对应于存储能力和重写能力逐级增强的计算模型。同一时期,编程语言的发展催生了对显式语法描述的需求。约翰·巴科斯在 1959 年的工作中使用的记法,以及彼得·瑙尔对 1960 年《ALGOL 60 报告》的编辑工作,推动了上下文无关文法成为语言规约的实用工具。
20 世纪 60 年代,自动机、逻辑、代数和语法分析之间建立起重要联系。尤利乌斯·布奇、卡尔文·埃尔戈特和鲍里斯·特拉赫滕布罗特的研究确立了有限自动机与符号串的逻辑描述之间的对应关系。马塞尔-保罗·许岑贝格尔于 1965 年利用非周期幺半群刻画无星语言,为正则语言的精细代数分类开辟了道路。语法分析研究将识别理论转化为编译器技术,后续研究则把这一领域拓展到树自动机、无穷字、加权系统和定量模型。
当前活跃的研究既关注表达能力,也关注使用简洁描述的代价。两种形式体系可能描述相同的语言,但其最小描述的大小却可能相差指数级,因此,相互转换和优化并非易事。对于更丰富的自动机和文法模型,等价性、包含关系及资源需求等问题仍是研究的核心。确定性与非确定性线性有界计算之间的关系尚未解决,这表明即使是经典层级中,也仍然存在基础性问题。
从样例中学习语言,则为这一领域增添了另一个维度。在某些学习模型中,仅凭正例进行不受限制的推断是不可能的,但精确的成员资格信息、反例和结构限制,可以使某些语言类变得可学习。在验证应用中,自动机被用于推断系统行为和构造抽象;而受文法约束的生成研究,则将语言识别与概率序列模型相结合。这类约束可以强制输出符合指定的语法;至于生成的表达式是否真实、恰当,或其行为是否正确,仍是独立的语义问题。