形式语言与自动机理论-02-正则语言及正则表达式

正:不偏斜;则:模范;正则:正规。

私以为,以正则翻译 "Regular Languages" 中的 "Regular" 不恰当,应取其 “常规” 之意,翻译为常规语言,因其定义简单而这样的语言对其中可包含的字符串限制较少。然而本文将按习俗使用公认的翻译“正则语言”。

一个语言被称为是“正则的”,若其可以用 \(\Sigma\) 中的元素(视这些元素分别为长度为 1 的字符串), \(\{\varepsilon\}\), \(\emptyset = \{\}\),以及并,串联及封闭运算定义。

注意,我们并不允许交,补以及幂运算。虽然有些(并非全部)使用了交,补的定义的语言有等价的正则的定义,而幂运算可以写作多次连续的串联运算。

定义正则语言的表达式称为正则表达式。

稍后将证明并非所有语言都是正则的。

需要注意的是,应用计算机领域使用 “正则表达式” 这个词来代表具有更多功能的表达式。这些功能有些有等价的真正正则的定义,例如 \(L^+\) 可定义为 \(L \cdot L^*\)\(L?\)(意为有或没有)可定义为 \(L + \{\varepsilon\}\)1 而有一些功能则超出了正则表达式的能力范围,其所定义的语言不一定存在等价的正则的定义。另外,本系列文章讨论的正则表达式的意义在于判定给定字符串是否属于某语言集合,而应用计算机领域使用的 “正则表达式” 则有匹配子字符串的功能。后文对这样的 “正则表达式” 再加讨论。

我们约定,在描述正则语言时,三种正则运算的优先级由高至低为 \(*, \cdot, +\)。本系列文章仅在记录正则表达式时,出于排版方便将后缀 \(*\) 而非上标。

接下来的两个例子考虑 \(\Sigma = \{a, b\}\).

\((a + b)*\) 描述所有定义在 \(\Sigma\) 上的字符串。

\(a* + b* = \{\varepsilon, a, aa, \dots\} \cup \{\varepsilon, b, bb, \dots\} = \{\varepsilon, a, b, aa, bb, \dots\}\)

特别注意到,上述两个定义不等价,因为有 \(ab \in (a + b)^*\), \(ab \not\in a^* + b^*\).

接下来给出几个比较难的例子作为练习。这几个例子使用 \(\Sigma = \{a, b\}\)。鼠标悬停或触摸黑色部分看答案。

所有有前缀 \(ababb\) 的字符串

\[ababb(a+b)*\]

所有有中缀 \(ababb\) 的字符串

\[(a+b)*ababb(a+b)*\]

长度为偶数的字符串

\[((a+b)(a+b))*\] 或者 \[(aa+ab+ba+bb)*\]

所有以一个 \(b\) 开头且长度为双数的语言

\[ \underbrace{b(a+b)}_{1} \underbrace{(aa + ab + ba + bb)*}_{2}\]

1: 单个 \(b\) 加上任何字母构成的长度为 2 的前缀

2: 后跟任意多个双字母组合

所有不以 \(ab\) 为后缀的字符串

\[ \underbrace{(a+b)*(aa+bb+ba)}_{1} \underbrace{+ a + b + \varepsilon}_{2} \]

1: 以 \(aa, bb, ba\) 为后缀的长度至少为 2 的字符串

2: 长度小于 2 的字符串肯定不以 \(ab\) 为后缀

不包含 \(aa\) 中缀的字符串

\[ \underbrace{(ab+b)*}_{1} \underbrace{(\varepsilon + a)}_{2} \]

1: 等价于 \((ab*)*\),必定以 \(b\) 结尾且不包含 \(aa\)

2: 前缀必定以 \(b\) 结尾因此还可以有至多一个 \(a\)。这里 \(\varepsilon\) 是多余的

不包含中缀 \(bb\) 的偶数长度的字符串

做不出来就算了【笑


  1. 此处不可定义为 \(L + \emptyset\),否则考虑 \((L_1+\emptyset) \cdot L_2 = L_1L_2 \ne (L_1L_2) + (L_2)\)↩︎