正则表达式

英文: Regular expressions.

正则表达式由 \(\Sigma\) 构成, 并通过正则操作组合得到.

正则语言 (Regular language)

正则语言是可以被有限自动机识别的语言.

正则操作是针对语言的运算符.

令 A, B 为语言:

并 (Union): \(A \cup B\).
连接 (Concatenation): \(A \circ B = \{xy \mid x \in A\ \land y \in B \} = AB\).
Kleene 星 (Kleene Star): \(A^* = \{x_1 ... x_k \mid \text{ each } x_i \in A \text{ for } k \ge 0\}\).

令 \(A = \{0, 1\}\), \(B = \{2, 3\}\):

\(A \cup B = \{0, 1, 2, 3\}\).
\(A \circ B = \{02, 03, 12, 13\}\)
\(A^* = \{\varepsilon, 0, 1, 01, 10, 11, 00, 001, ...\}\). (除非 \(A\) 是空集, 否则结果是无限集)

此处的闭包是数学中的术语, 而非计算机科学.

若对某个集合的成员进行一种运算, 生成的仍然是这个集合的成员, 则该集合被称为在这个运算下闭合. - Wikipedia

比如自然数在加法运算下闭合, 因为两个自然数相加所得到的结果一定是自然数.
但是自然数在减法运算下不闭合, 因为两个自然数相减可能得到非自然数的结果, 如负整数.

若 \(M_1\) 识别 \(A_1\), \(M_2\) 识别 \(A_2\), 则有一台 DFA \(M_3\) 能识别 \(A_1 \cup A_2\).

一个简单的思路是将输入分别交给 \(M_1\) 和 \(M_2\) 识别, 只要有一台自动机接受输入, 则 \(M_3\) 也接受.
但确定有限自动机无法直接实现这种操作, 因为确定有限自动机的运行 (即状态的转移) 需要消耗字符串中的字符, 因此无法多次尝试同一个字符串.

可行的方法是将两台自动机合并, 使他们并行处理一个字符串.

这意味着自动机 \(M_3\) 能在单个状态里同时表示 \(M_1\) 和 \(M_2\) 的状态:

\[ Q_3 = Q_1 \times Q_2 = \{ (q_1, q_2) \mid q_1 \in Q_1 \land q_2 \in Q_2 \} \\ q_0 = (q_1, q_2) \]

这里的并行指的是并行的执行状态的转移, 而非并行的单独模拟自动机:

\[ \delta((q, r), a) = (\delta(q, a), \delta(r, a)) \]

只要 \(q \in Q_1\) 或 \(r \in Q_2\), 该状态即为 \(M_3\) 的接受状态:

\[ F_3 = (F_1 \times Q_2) \cup (F_2 \times Q_1) \]

后续将使用非确定有限自动机来简化上述证明, 并证明另外两种正则操作的闭合属性.