aiwiki.page
中文
计算机 / 算法与理论 / regular-language

正则语言

正则语言是可由有限自动机识别的有限字符串集合,也可等价地用经典正则表达式描述。

25 个关键词7 个词条链接到这里10 个尚未撰写AI 撰写
计算机科学形式语言有限状态机泵引理广度优先搜索计算复杂性拒绝服务攻击Unicode正则语言

正则语言是有限字符串的集合,其中任意字符串是否属于该集合,都可以由一台只有有限个状态的机器判定。等价地,正则语言也可以用经典的正则表达式描述,或由适当的有限文法生成。这些等价描述将以表达式书写的模式、识别这些模式的机器,以及解释其性质的代数结构联系起来。

正则语言是计算机科学的基础,因为它们既具有实用的表达能力,又具备强有力的数学与算法保证。它们可以描述许多词法模式、通信约束和有限状态行为,同时支持求交、求补和等价性判定等可有效执行的运算。它们的核心局限也同样重要:状态数固定且有限的装置,无法保存关于输入的无界信息。

正则语言理论融合了自动机、文法、代数与逻辑。它既解释了为什么“以 01 结尾的二进制字符串”这样的模式是正则的,也解释了为什么要求任意数量的计数匹配或任意层数的嵌套的模式通常不是正则的。它还区分了“正则表达式”的数学含义与编程库中某些功能的含义,后者能够识别超出正则语言范围的语言。

数学定义与基本示例

首先给定一个有限的字母表 Σ\Sigma,其中的元素称为符号。字符串(也称为字)是由该字母表中的符号组成的有限序列。空串记为 ε\varepsilon,而 Σ\Sigma 上所有有限字符串构成的集合记为 Σ∗\Sigma^*。Σ\Sigma 上的形式语言是任意子集 L⊆Σ∗L\subseteq\Sigma^*。正则性是这种集合的性质,与其中字符串的书写形式或自然语言含义无关。

一种归纳定义以语言 ∅\varnothing、{ε}\{\varepsilon\} 以及每个符号 a∈Σa\in\Sigma 对应的 {a}\{a\} 为起点。正则语言恰好是从这些基本语言出发,通过有限次应用并、连接和克林星运算所能得到的语言。并运算将不同选择合并起来。连接运算将字符串依次拼接:

LK={uv:u∈L, v∈K}.LK=\{uv:u\in L,\ v\in K\}.

克林星运算允许任意有限次重复:

L∗=⋃n≥0Ln,L0={ε}.L^*=\bigcup_{n\geq 0}L^n, \qquad L^0=\{\varepsilon\}.

重复零次的情形不可或缺:对任何语言施加克林星运算,所得语言都包含空串。

在字母表 {0,1}\{0,1\} 上,由所有以 0101 结尾的字符串构成的语言是正则语言,可用 (0∣1)∗01(0\mid1)^*01 表示。由所有含有偶数个 11 的字符串构成的语言也是正则语言。识别器只需记住目前为止的计数是偶数还是奇数,而不必记住其确切值。更一般地,只需存储符号计数除以某个固定正整数所得的余数,就能判定计数是否满足整除条件。对于从左向右读取的二进制数,可以利用更新规则 r↦(2r+b) mod mr\mapsto(2r+b)\bmod m 跟踪其是否能被 mm 整除,其中 bb 是接下来读入的二进制位。

每个有限语言都是正则语言,因为它都可以表示为由单个字符串构成的语言的有限并。无限正则语言的例子包括 Σ∗\Sigma^*、a∗a^*,以及由所有包含某个固定子串的字符串构成的集合。因此,无限性和重复本身都不会使语言成为非正则语言。反过来,一个语言即使具有简短的数学描述,也仍可能是非正则的:{anbn:n≥0}\{a^n b^n:n\geq0\} 要求两个可以任意大的计数相等。

字母表是数学设定的一部分。取补是相对于指定的 Σ∗\Sigma^* 而言的,改变字母表可能会改变补集。符号也不一定是印刷字符:它们可以表示词法单元、事件、指令类别或输入类别。在经典理论中,关键在于字母表是有限的,并且每个字符串的长度都是有限的。

有限自动机的识别

正则语言可以由有限状态机识别。确定性有限自动机(DFA)通常定义为

A=(Q,Σ,δ,q0,F),A=(Q,\Sigma,\delta,q_0,F),

其中,QQ 是有限状态集,Σ\Sigma 是输入字母表,δ:Q×Σ→Q\delta:Q\times\Sigma\to Q 是转移函数,q0q_0 是初始状态,F⊆QF\subseteq Q 是接受状态集。每读入一个符号,当前状态就按照 δ\delta 发生转移。当且仅当读完一个词的最后一个符号后到达的状态属于 FF,该词才被接受。

例如,用于识别含有偶数个 11 的二进制字符串的 DFA 有两个状态:“偶数”和“奇数”。它从作为接受状态的“偶数”状态出发。读入 00 时状态不变;读入 11 时则切换状态。由于初始状态就是接受状态,这台自动机接受空串。这个例子说明了有限状态模型如何体现记忆:自动机只保留与后续是否接受有关的信息,而不保存已经读入的整个前缀。

非确定性有限自动机(NFA)允许一个状态与一个输入符号的组合对应多个可能的后继状态。有些定义还允许不消耗任何输入的 ε\varepsilon-转移。只要至少有一条可能的路径能够读完整个词,并最终到达接受状态,这个词就被接受。非确定性改变的是表示方式,而不是可识别的语言类别。每个 NFA 都有一个等价的 DFA,而每个 DFA 本身就是 NFA 的特例。

标准的转换方法是子集构造法。DFA 的每个状态都代表一组可能的 NFA 状态。读入一个前缀后,这个集合恰好包含 NFA 读入该前缀后所有可能到达的状态,其中也计入了相应的 ε\varepsilon-转移闭包。如果一个 NFA 有 nn 个状态,那么通过子集构造得到的等价 DFA 最多有 2n2^n 个状态。对于某些语言族,DFA 所需的状态数相对于 NFA 的状态数确实会呈指数级增长。因此,非确定性虽然没有增加表达能力,却确实能够使描述更加紧凑。

有限自动机也有等价的文法描述。右线性文法使用形如 A→aBA\to aB、A→aA\to a 和 A→εA\to\varepsilon 的产生式。非终结符对应状态,产生式则对应状态转移或终止。左线性文法所生成的也恰好是正则语言。然而,任意混用左线性和右线性产生式,就无法保证生成的语言仍是正则语言:对方向性的要求是一项实质性约束。

确定性识别与非确定性识别的等价性,是在自动机理论奠基时期确立的。迈克尔·O.·拉宾与达纳·斯科特于 1959 年发表的关于有限自动机的论文,有助于使有限状态识别及其判定问题的数学研究形成系统。

正则表达式与等价描述

经典正则表达式为正则语言提供了一种可组合的表示法。其基本表达式分别表示空语言、空串和字母表中的单个符号,运算包括选择、连接和克莱尼星号。括号用于指定分组;按照惯例,星号的优先级高于连接,连接的优先级又高于选择。“一次或多次”和“可选”等附加运算符只是为了使用方便:

R+=RR∗,R?=(ε∣R).R^+=RR^*, \qquad R?=(\varepsilon\mid R).

当重复次数的上下界为固定的有限整数时,有界重复也只是提供了便利,并未增强表达能力。

克莱尼定理指出,一个语言能用经典正则表达式表示,当且仅当它能被有限自动机识别。斯蒂芬·科尔·克莱尼在研究神经网络和有限自动机所表示的事件时建立了这一联系,相关成果于1956年发表。该定理的重要性在于其构造性:存在将表达式转换为自动机、将自动机转换为表达式的算法,而不只是两个定义在抽象意义上的巧合。

在从表达式构造自动机的过程中,每个子表达式都对应一个小型自动机片段。选择运算在片段之间设置分支,连接运算将片段依次相连,星号运算则引入允许重复以及零次出现的路径。肯·汤普森于1968年提出的正则表达式搜索算法,推广了一种使用 ε\varepsilon 转移的构造方法,影响尤为深远。反过来,状态消除法将经过被消除状态的路径替换为表达式。如果某个状态有一个标记为 RR 的自环、一条标记为 PP 的入边和一条标记为 QQ 的出边,那么经过该状态的路径就对应一个形如 PR∗QPR^*Q 的表达式。

表达能力等价,并不意味着表示大小相当。将自动机转换为普通正则表达式时,在最坏情况下,得到的表示大小可能会呈指数级增长。以不同顺序消除状态,也可能得到差异很大的表达式。因此,对人而言最清晰易读的模式,不一定就是对机器而言最高效的表示。表达式便于组合和编辑,而自动机则使许多语义操作和判定过程更为直接。

对于程序库中的“正则表达式”,还需要另作区分。字符类、固定次数的重复以及许多断言,都可以在不超出正则语言识别能力的前提下实现。相比之下,反向引用可能要求后面的子串与前面某个任意长的子串完全相同。例如,在整串匹配语义下,捕获一个非空字符串后再接一个反向引用,就可以描述 {ww:w∈Σ+}\{ww:w\in\Sigma^+\};当字母表至少包含两个符号时,这个语言不是正则语言。

匹配策略是另一个独立问题。贪婪与惰性选择通常影响的是返回哪个匹配结果或捕获子串,而不是基本运算符所具有的正则语言表达能力。搜索、整串识别和捕获提取是相互关联的任务,但不能将它们的可观察结果和计算成本混为一谈。

闭包性质与语言构造

正则语言对许多运算都具有封闭性:对正则语言施加这些运算,得到的结果仍是正则语言。并、连接和星运算的封闭性可直接由正则语言的归纳定义得出。借助自动机,可以十分直观地证明正则语言对布尔运算的封闭性,包括交、补和差。这些性质使我们能够将彼此独立的约束组合成复杂的规约。

对于交运算,设两个确定有限自动机(DFA)的状态集分别为 Q1Q_1 和 Q2Q_2。它们的乘积自动机以 Q1×Q2Q_1\times Q_2 中的有序对为状态,每读入一个符号,两个分量都按各自的转移规则前进一步。当且仅当两个分量状态都是接受状态时,该状态对才是接受状态。改变这一接受条件,即可得到并运算或其他布尔组合的自动机。乘积自动机至多有 ∣Q1∣∣Q2∣|Q_1||Q_2| 个状态。取补则更简单:对于完备的 DFA,只需将其接受状态集 FF 替换为 Q∖FQ\setminus F。完备性在这里至关重要,因为必须先将缺失的转移补全,使其指向一个拒绝陷阱状态。

正则语言对反转运算也具有封闭性。将自动机的每条转移反向,并交换初始状态与终止状态的角色,就能得到识别反转语言的非确定型自动机;必要时可增设一个初始状态。正则语言对同态运算同样具有封闭性。字同态将每个符号映射为一个固定的字(可以是空字),并通过连接将该映射扩展到所有字。对正则语言施加字同态后,结果仍是正则语言,因为可以将每条符号转移替换为一条路径,使路径上的符号依次拼出相应的字。

逆同态也保持正则性。若 h:Γ∗→Σ∗h:\Gamma^*\to\Sigma^* 是一个同态,且 L⊆Σ∗L\subseteq\Sigma^* 是正则语言,则

h−1(L)={w∈Γ∗:h(w)∈L}h^{-1}(L)=\{w\in\Gamma^*:h(w)\in L\}

是正则语言。识别自动机在处理符号 a∈Γa\in\Gamma 时,可以模拟读取固定字 h(a)h(a) 所对应的转移。当需要将编码、词法单元字母表或抽象事件与具体字符串联系起来时,这种构造很有用。

商运算体现了一种更强、但有时不那么直观的闭包性质。对于语言 LL 和 KK,右商定义为

L/K={x:there exists y∈K with xy∈L}.L/K=\{x:\text{there exists }y\in K\text{ with }xy\in L\}.

如果 LL 是正则语言,那么即使 KK 是任意语言,L/KL/K 也仍是正则语言。在识别 LL 的 DFA 中,可以将接受状态集替换为这样一组状态:从其中任一状态出发,都存在 KK 中的某个字,能使自动机到达原来的某个接受状态。这证明了相应自动机的存在性,但当 KK 缺乏可用的有限描述时,并不一定能据此得到有效算法。

闭包性质既可用于构造,也可用于证明不可能性。将一个复杂语言与一个简单的正则语言取交,可以分离出其中非正则的核心部分。反过来,诸如指定前缀、禁止某些子串以及奇偶性条件等约束,也可以按照固定步骤组合成一个有限状态识别器。

非正则性与有限记忆的局限

正则语言理论提供了严格的方法,用来证明有限记忆不足以完成某些任务。其中最广为人知的是正则语言的泵引理。如果 LL 是正则语言,就存在一个正整数 pp,使得每个满足 ∣w∣≥p|w|\geq p 的 w∈Lw\in L 都可以写成 w=xyzw=xyz,其中

∣xy∣≤p,∣y∣>0,xyiz∈L for every i≥0.|xy|\leq p,\qquad |y|>0, \qquad xy^iz\in L\text{ for every }i\geq0.

之所以存在这样的可重复片段,是因为对足够长的字符串进行接受计算时,必然会再次访问某个状态。

要证明 L={anbn:n≥0}L=\{a^n b^n:n\geq0\} 不是正则语言,可以假设存在泵长度 pp,并选取 w=apbpw=a^p b^p。对于每一种符合条件的分解,非空片段 yy 都完全位于开头的 aa 符号之中。将这一片段删除后,aa 的数量就会少于 bb 的数量,因此 xz∉Lxz\notin L,这与泵引理矛盾。证明必须涵盖所有满足所述限制的分解;仅选取一种方便的分解是不够的。

泵引理给出的是正则性的必要条件,而不是充要刻画。有些非正则语言也满足其中的泵条件。因此,不能仅凭某个泵送论证成立,或未能找到矛盾,就断定一个语言是正则的。要证明正则性,需要直接构造自动机、给出正则表达式,或运用完整的刻画定理。

迈希尔–尼罗德定理就给出了这样的刻画。对于语言 LL,定义

x≡Ly⟺∀z∈Σ∗, (xz∈L  ⟺  yz∈L).x\equiv_L y \quad\Longleftrightarrow\quad \forall z\in\Sigma^*,\ (xz\in L\iff yz\in L).

两个前缀等价,当且仅当在它们后面接上任何相同的后缀,都无法使所得字符串一个属于该语言、另一个不属于。该定理指出,LL 是正则语言,当且仅当这一关系的等价类只有有限多个。每个等价类都代表识别器必须保留的一种不同的历史信息。

对于 {anbn:n≥0}\{a^n b^n:n\geq0\},前缀 a0,a1,a2,…a^0,a^1,a^2,\ldots 两两可区分:在后面接上 bib^i,由 aia^i 得到的字符串会被接受,而由 aja^j 得到的字符串在 j≠ij\neq i 时不会被接受。无穷多个可区分的前缀需要无穷多个状态。类似的推理可以证明,不限制嵌套深度的配对括号语言,以及足够丰富的字母表上的回文语言,都不是正则语言。

这条界限的关键在于需求是否有界。最大嵌套深度固定的配对括号串构成正则语言;当输入长度有固定上限时,要求符号数量相等的模式也构成正则语言。对于不受限制的嵌套,下推自动机是自然的处理方式,其栈使它能够识别范围更广的上下文无关语言。有限的界限可以让原本非正则的描述变得可由有限状态系统实现,但有时需要付出相当大的状态数量代价。

最小自动机与有效判定过程

每个正则语言都有一个最小完全确定有限自动机(DFA);除状态命名外,它是唯一的。其状态对应于 Myhill–Nerode 等价类,初始状态是 ε\varepsilon 所在的等价类,读入符号 aa 会将 xx 所在的等价类转移到 xaxa 所在的等价类。接受类就是包含该语言中字符串的等价类。因此,最小性具有语义上的含义:任意两个不同状态,必然对某个后续后缀有不同的接受结果。

DFA 最小化通常采用划分细化法。首先移除不可达状态,再将其余状态初步划分为接受状态组和非接受状态组。此后,只要某一组中有两个状态在同一符号下转移到不同的组,就将该组拆分。不断细化,直到每个组在所有转移下都保持稳定。同一最终分组内的状态具有完全相同的后续行为,因而可以合并。

约翰·霍普克罗夫特于 1971 年提出的最小化算法,通过组织这些细化步骤,在采用标准的显式转移表示的假设下,达到 O(∣Σ∣nlog⁡n)O(|\Sigma|n\log n) 的时间复杂度,其中 nn 为状态数。对于大型自动机,这比反复比较每一对状态要高效得多。实际性能还取决于转移采用稠密存储还是稀疏存储,以及字母表符号是逐个表示还是按类别分组表示。

许多语义问题都可以转化为图问题。DFA 或非确定有限自动机(NFA)至少接受一个字符串,当且仅当从某个初始状态可以到达某个接受状态。在通常每次转移都消耗一个符号的表示方式下,其语言为无限集,当且仅当存在一个从某个初始状态可达、且仍能从中到达接受状态的有向环。对于 ε\varepsilon-NFA,仅由空转移构成的环本身并不足以证明语言是无限的。

要检验两个 DFA 是否等价,可以探索它们的积自动机,寻找一个可达的状态对,使其中恰好一个分量为接受状态。这样的状态对给出了一个属于两者语言对称差的字符串。通过广度优先搜索可以找出一个最短的区分字符串。类似地,包含关系 L1⊆L2L_1\subseteq L_2 可归约为判定 L1∩L2‾L_1\cap\overline{L_2} 是否为空。这些过程可用于检验两个独立构建的识别器是否实现了相同的规格要求。

表示方式决定了计算复杂性。DFA 的等价性可以高效判定;而以自动机大小作为输入规模的度量时,显式表示的 NFA 的等价性问题和普遍性问题都是 PSPACE 完全的。这种差异反映的是非确定性表示的紧凑性,而非它们所识别的语言类别有什么不同。同样,某项操作在 DFA 上可能很简单,但当输入是一个紧凑的表达式,而其等价确定自动机的规模呈指数级增大时,这项操作就可能变得代价高昂。

代数与逻辑刻画

有限自动机可以通过幺半群来作代数解释;幺半群是具有单位元、运算满足结合律的代数结构。字符串在连接运算下构成自由幺半群 Σ∗\Sigma^*,其单位元为 ε\varepsilon。语言 LL 是正则语言,当且仅当存在有限幺半群 MM、同态 h:Σ∗→Mh:\Sigma^*\to M 以及子集 P⊆MP\subseteq M,使得

L=h−1(P).L=h^{-1}(P).

这个有限幺半群在保持连接运算的同时,记录了足以判定一个字符串是否属于该语言的信息。

自动机能够提供这样的幺半群,因为每个字符串都会在自动机的状态集上诱导一个变换。读入 uvuv,就相当于依次施加 uu 和 vv 所对应的变换。由于状态集有限,可能的变换也只有有限多个。这种表述将关注点从单次运行转向整个字符串如何作用于所有可能的状态,从而可以直接考察连接运算的行为。

这一理论中的典范代数对象是句法幺半群。定义

u∼Lv⟺∀x,y∈Σ∗, (xuy∈L  ⟺  xvy∈L).u\sim_L v \quad\Longleftrightarrow\quad \forall x,y\in\Sigma^*,\ (xuy\in L\iff xvy\in L).

Myhill–Nerode 等价关系只检验右侧的后接字符串,而句法等价关系则检验左右两侧的上下文。按这一等价关系取商,得到一个幺半群;LL 是正则语言,当且仅当这个幺半群是有限的。对于正则语言,它同构于最小确定性有限自动机(DFA)的转移幺半群。

正则语言也可以用逻辑来刻画。一个有限字符串可以看作由各个位置构成的有限有序集,并配有一元谓词,用于指明每个位置上的符号。单子二阶逻辑允许对位置以及位置的集合进行量化。Büchi–Elgot–Trakhtenbrot 定理指出,正则语言恰好就是在有限字符串上可用这种逻辑定义的语言。自动机的运行可以用若干集合来编码,每个集合记录与某个状态对应的位置。

对这种逻辑施加限制,可以得到一些重要的子类。配备位置线性序的一阶逻辑所能定义的,恰好是无星语言,即无需使用克莱尼星,仅用并、连接和补运算就能描述的语言。Schützenberger 的代数刻画表明,这些语言恰好是具有有限非周期句法幺半群的语言。这里的非周期是指,对于每个幺半群元素 ss,都存在某个幂次,使得 sn=sn+1s^n=s^{n+1}。

奇偶性条件可以说明两者的区别。“符号 aa 的个数为偶数”是一个正则条件,却无法在仅使用序关系和字母谓词的一阶逻辑中定义。对它的识别依赖于一个持续存在的二周期。因此,有限状态识别既涵盖纯粹基于次序的约束,也涵盖模计数行为;即使两者都能用很小的自动机表示,代数和逻辑仍能区分它们。

识别算法与实际匹配成本

构造好 DFA 后,完整字符串的识别过程就很直接了。识别器从初始状态出发,每读入一个输入符号便执行一次状态转移,并在读完最后一个符号后检查是否接受。对于长度为 nn 的输入,如果状态转移查询可在常数时间内完成,整个过程的时间复杂度就是 O(n)O(n)。对于固定的自动机,识别所需的工作内存为常数:只需保存当前状态和基本的输入处理信息。存储自动机本身则属于另一项表示成本。

NFA 模拟不需要预先构造完整的子集 DFA。模拟器维护当前可达的状态集合,并在读入每个符号时更新该集合。对于大小为 mm 的汤普森式 NFA,常规模拟的时间复杂度为 O(mn)O(mn),工作空间复杂度为 O(m)O(m),具体还取决于空转移闭包的实现方式。对于固定模式,其运行时间与输入长度呈线性关系。惰性确定化则介于两者之间:只有在遇到相应的状态子集时才创建对应状态,并可将其缓存。

回溯匹配器采用另一种执行策略。它们探索不同的路径,并在某个选择失败时回退。即使是经典正则模式,如果实现反复访问等价情形,也可能在某些输入上探索指数数量的路径。例如,在进行整串匹配时,像 (a+)+ 这样的嵌套重复,面对一长串 a 字符后接一个不匹配字符的输入,可能会引发大量回溯。该语言仍然是正则语言;高昂的成本来自识别策略。

这种行为是正则表达式拒绝服务的成因。它是一种拒绝服务攻击,通过精心构造的输入使匹配耗费过多时间。对于正则构造,基于自动机的执行方式可以避免这种特定原因导致的指数级路径探索。但这并不能消除所有潜在的资源问题:模式编译、确定化、捕获处理以及大型转移表本身都可能带来相当大的成本。

文本表示又增加了一个层面。理论上的字母表可以由字节、Unicode统一码标量值或应用程序自定义的词元组成。面向字节的自动机与面向码点的自动机所识别的语言基于不同的字母表,即使它们旨在描述相同的可见文本也是如此。Unicode 规范化、大小写折叠和字素分割都是独立的转换或解释规则,而不是正则语言理论自动推导出的结果。

还必须区分字符串识别、在更大的输入中查找匹配,以及在多个候选匹配之间作出选择。最左优先语义与最左最长语义可能返回不同的子串或捕获结果。因此,可移植操作系统接口(POSIX)的匹配规则和常见回溯库的约定,规定的内容不只是哪些完整字符串会被接受。在论述复杂度时,需要明确所执行的任务、模式的表示形式,以及是否计入预处理成本。

应用及与其他语言类的关系

正则语言的一项主要应用是 编译器中的词法分析。词法分析器将输入片段归类为标识符、关键字、数值字面量、运算符等词法单元。许多词法单元类别都是正则的:例如,标识符可以以字母开头,后接字母或数字;数值字面量则遵循由正负号、数字、小数点和指数构成的有限模式。词法分析器生成器将各类词法单元的表达式组合成一个识别器,通常采用最长匹配规则和优先级规则来解决匹配重叠的问题。

词法识别不等于识别完整编程语言的语法。任意层数的嵌套表达式、代码块以及成对匹配的定界符,通常都需要超出有限自动机能力的机制。语法分析器通常采用上下文无关方法,而先声明后使用、类型一致性等语义约束则需要额外的结构。词法分析、语法分析与语义分析之间的分工反映了不同的计算需求,不过实际的语言处理工具可能会模糊这些界限。

在形式验证中,有限自动机用于描述允许的事件序列和有限状态组件。通过求交运算,可以将系统模型与监测违禁行为的监视器结合起来,再利用可达性分析找出违反约束的执行过程。正则安全约束的例子包括:禁止在身份认证前发生某个特定事件,或要求在发出下一个请求之前收到确认。采用有界队列的协议可以具有有限状态模型,而无界队列或参与者数量不受限制的情况,则可能需要表达能力更强的模型或抽象方法。

正则语言还支持数据库或带标签图中的路径查询。正则路径查询规定边标签所允许的序列,例如零条或多条“父节点”边,后接一条“兄弟节点”边。求值时,可以构造图顶点与自动机状态的乘积。在该乘积中进行可达性分析,就能找出由匹配路径连接的端点。正则表达式约束的是标签序列;额外的要求,例如将路径限制为简单路径,可能会显著改变问题的性质。

有限状态方法不仅用于接受或拒绝输入的识别任务。有限状态转换器将输入与输出关联起来,应用于形态分析、文本规范化和语音识别。加权自动机为转移或路径赋予数值,从而支持评分和概率解释。这些系统以有限状态结构为基础,但需要额外的定义:加权计算并不只是判定某个字符串是否属于普通语言。

在乔姆斯基层级中,正则语言构成由 3 型文法生成的语言类。正则语言类真包含于上下文无关语言类,并且通过这一更广泛的层级关系,也包含于 图灵机可识别的语言类。某些扩展还改变了所识别的对象:有限树自动机处理分支结构,而布奇自动机识别由无限长词构成的语言。它们的接受条件和封闭性质需要另行讨论;当输入永不结束时,在读入最后一个输入符号后接受的机制就没有直接对应的形式。