1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
| 有限自动机（Finite Automata，简称 **FA** 或 FSM）是一种基础的计算模型。它拥有**有限数量的状态**，并且**没有额外的可读写存储**。自动机从初始状态出发，逐步读取输入字符串的每个符号，根据**当前状态**和**输入符号**通过**状态转移函数**切换到**下一个状态**。输入处理完毕后，若停在某个**接受状态**，则该字符串被自动机接受。
它的主要任务是**判断**一个**给定的输入字符串** $w$ 是否属于**它所定义的语言** $L(M)$, 即 $w \in L(M)$。 这里的$L(M)$ 也就是该自动机对应的**正则语言**。
有限自动机分为两类：**确定性有限自动机** (DFA) 和**非确定性有限自动机** (NFA)。
### 确定性有限自动机 (DFA)
确定性有限自动机（DFA）在每一步计算中，当前状态和输入符号**唯一决定**下一个状态。
**形式化定义：**
DFA 可表示为五元组 $M = (K, \Sigma, \delta, s, F)$，其中：
- $K$：有限状态集合, $K = \{q_0, q_1, \ldots, q_{n-1}\}$
- $\Sigma$：输入字母表, 一个有限符号集合, 如 $\Sigma = \{a, b\}$
- $\delta$：状态转移函数，$\delta: K \times \Sigma \to K$ , 定义了在状态 $q \in K$ 下读取输入符号 $a \in \Sigma$ 时，自动机转移到的下一个状态 $\delta(q, a)$
- $s \in K$：初始状态, $M$ 开始计算时所在的状态
- $F \subseteq K$：接受状态集合, 如果计算结束时自动机停在 $F$ 中的某个状态，则输入字符串被接受。
需要注意的是, 假如已知 $M$ 接受 $L$ , 它的补集 $\overline{L}$ 也可以被一个DFA接受, 只需将 $M$ 的接受状态和非接受状态互换即可。
#### 运算过程
我们已经定义了机器的结构，现在来看它的运算过程。
- **配置 (Configuration)：** DFA 的配置由**当前状态**和**尚未读取的输入字符串**组成，记为序对 $(q, w)$。
- **一步产生关系 ($\vdash_M$)：** 若机器在状态 $q$，输入字符串为 $aw'$，且 $\delta(q, a) = q'$，则 $(q, aw') \vdash_M (q', w')$，表示机器从配置 $(q, aw')$ 一步转移到 $(q', w')$。
- **多步产生关系 ($\vdash_M^*$)：** 表示零步或多步的产生关系，是 $\vdash_M$ 的**自反传递闭包**。例如，$(n, WSSW) \vdash_M^* (n, \epsilon)$ 表示从初始状态 $n$ 处理完整输入 $WSSW$ 后停在状态 $n$。
- **字符串的接受：** 字符串 $w$ 被 $M$ 接受，当且仅当，从初始配置 $(s, w)$ 出发，经过若干步计算到达某个配置 $(q, \epsilon)$，且 $q$ 属于接受状态集合 $F$。
### 非确定性有限自动机 (NFA)
非确定性有限自动机（NFA）允许在**某个状态**和**输入符号**下有**多个可能的下一个状态**，也可能**没有可选状态**（计算终止）。NFA 还支持 $\varepsilon$-转移，即可以在**不消耗输入符号的情况下进行状态转换**。即 NFA 的三大特点：多重选择, 没有选择, 空串转移。
**接受条件：**
一个字符串 $w$ 被 NFA 接受，当且仅当存在**至少一条合法的计算路径**，在消耗完 $w$ 后，自动机停在某个接受状态。
如上的正则表达式要识别 $L=(ab \cup aba)^*$ , 可以选择DFA来实现, 但是显然状态数更多, 可读性更差. 而使用NFA可以更简洁地表示该语言.
> 在DFA中, 像 $q_4$ 这样的状态，虽然在识别正确的语言中没有使用到, 但是仍然具有非常重要的功能，它通常被称为死状态（Dead State）或陷阱状态（Trap State）。
> 当自动机进入死状态后，无论接收到什么输入符号，都会一直停留在该状态，无法再转移到其他状态。死状态的存在保证了 DFA 的确定性和完整性，并处理无效的输入序列。
对于NFA, 其形式化定义与DFA类似, 但**状态转移函数**有所不同: DFA的状态转移函数 $\delta$ 是一个确定性的映射，而 NFA 的状态转移函数 $\delta$ 则是一个**非确定性的映射**(或者说是一种**关系**)，允许多个可能的下一个状态。
NFA 可表示为五元组 $M = (K, \Sigma, \delta, s, F)$，其中：
- $K$：有限状态集合, $K = \{q_0, q_1, \ldots, q_{n-1}\}$
- $\Sigma$：输入字母表, 一个有限符号集合, 如 $\Sigma = \{a, b\}$
- $\delta$：状态转移函数，$\delta: K \times (\Sigma \ \cup \{\varepsilon\}) \to P(K)$ , 定义了在状态 $q \in K$ 下读取输入符号 $a \in \Sigma$ 或 $\varepsilon$ 时，自动机可以转移到的**下一个状态集合** $\delta(q, a) \subseteq K$
- $s \in K$：初始状态, $M$ 开始计算时所在的状态
- $F \subseteq K$：接受状态集合, 如果计算结束时自动机停在 $F$ 中的某个状态，则输入字符串被接受。
至于其运算过程, 与DFA类似, 只是需要考虑多条路径的情况.
### DFA 与 NFA 的等价性
DFA 和 NFA 在**描述语言的能力**上是完全等价的。也就是说，任何可以被 NFA 接受的语言，也可以被某个等价的 DFA 接受，反之亦然。
且任意DFA都可以转换为等价的NFA, 反之亦然. 但NFA转换为DFA时, 可能会导致状态数指数级增长.
首先, 任意DFA都可以看作是特殊的NFA, 因为DFA的每个状态和输入符号下只有一个确定的下一个状态, 这正是NFA的一种特例. 而证明NFA可以转换为DFA, 我们需要使用下面的子集构造法
**证明核心：子集构造法 (Subset Construction)**
首先, DFA和NFA有两个重要的区别:
1. NFA允许多个可能的下一个状态，而DFA在每一步只有一个确定的下一个状态。也就是两者的形式化定义中, 状态转移函数 $\delta$ 的不同:
- 对于DFA: $\delta: K \times \Sigma \to K$
- 对于NFA: $\delta: K \times (\Sigma \cup \{\varepsilon\}) \to P(K)$
2. NFA允许$\varepsilon$-转移，而DFA不允许。即:
- 对于DFA: 没有$\varepsilon$-转移
- 对于NFA: 允许$\varepsilon$-转移, 即 $\delta(q, \varepsilon)$ 可以非空
下面我们的转换的核心就是处理这两个区别.
我们不再追踪 NFA “可能”处于的单一状态，而是追踪它在任何时刻“可能处于的所有状态的集合”。具体来说，**子集构造法**的核心思想是：构造一台新的 DFA，使其每个状态都对应于原 NFA 的一个**状态集合**。
> 为了解决 NFA 中的 $\varepsilon$-转移（即无需消耗输入即可转移），我们引入$\varepsilon$-闭包（epsilon-closure），记作 $E(q)$。$E(q)$ 表示：从**状态 $q$ 出发**，**仅通过 $\varepsilon$-转移**（不读取任何输入），能够到达的**所有状态的集合**（包括 $q$ 本身）。
#### 子集构造法步骤
假设有一台 NFA $M$，我们要构造一台等价的 DFA $M'$，其定义如下：
- **状态集 $K'$**：$M'$ 的每个状态是 $M$ 的状态集的一个子集（即 $K'$ 是 $K$ 的幂集）。
- $K' = P(K) = 2^K$
- 从这里可以看出, 如果NFA有 $n$ 个状态, 则对应的DFA最多有 $2^n$ 个状态, 也就是复杂度的指数级增长. 不过很多状态是不可达的, 因此实际状态数通常远**小于 $2^n$**.
- **初始状态 $s'$**：$M'$ 的初始状态是 $M$ 的初始状态 $s$ 的 $\varepsilon$-闭包，即 $E(s)$。
- $s' = E(s)$
- **字母表 $\Sigma$**：与 NFA 相同。
- **转移函数 $\delta'$**：对于 $M'$ 的任意状态 $Q \subseteq K$ 和输入符号 $a$，其转移定义为：$\delta'(Q, a) = \bigcup_{q \in Q} E(\delta(q, a))$
1. 对 **$Q$ 中每个状态 $q$**，计算 $q$ 读入 $a$ 后能到达的所有状态的集合 $S$。
2. 对 $S$ 中每个状态，取其 **$\varepsilon$-闭包**。
3. 取所有这些 $\varepsilon$-闭包的**并集**，作为 $M'$ 在 $Q$ 读入 $a$ 后的下一个状态。
- 一般来说, DFA 的状态集 $K'$ 是通过一种按需计算的方式构建的。从起始状态开始, 根据输入符号逐步计算和添加新的状态子集, 接着利用得到的状态子集继续计算, 直到不再有新的状态子集被发现为止。
- **接受状态 $F'$**：$M'$ 的接受状态集合是**所有**包含 $M$ 至少一个接受状态的状态子集。
- $F' = \{Q \subseteq K \mid Q \cap F \neq \emptyset\}$
这种方法保证了 DFA 能“模拟”NFA 的所有可能路径，从而接受与原 NFA 相同的语言。
#### 示例
**第一步：NFA $M$ 定义整理与 $\varepsilon$-闭包预计算**
- 状态集 $K$：$\{q_0, q_1, q_2, q_3, q_4\}$
- 字母表 $\Sigma$：$\{a, b\}$
- 起始状态 $s$：$q_0$
- 接受状态 $F$：$\{q_4\}$
- 转移关系 $\Delta$：
- 非 $\varepsilon$ 转移：
- $\delta(q_0, b) = \{q_2\}$
- $\delta(q_2, b) = \{q_4\}$
- $\delta(q_1, a) = \{q_0, q_4\}$
- $\delta(q_3, a) = \{q_4\}$
- $\varepsilon$ 转移：
- $\delta(q_0, \varepsilon) = \{q_1, q_2, q_3\}$
- $\delta(q_1, \varepsilon) = \{q_2, q_3\}$
- $\delta(q_4, \varepsilon) = \{q_3\}$
- $\varepsilon$-闭包计算：
- $E(q_2) = \{q_2\}$
- $E(q_3) = \{q_3\}$
- $E(q_4) = \{q_3, q_4\}$
- $E(q_1) = \{q_1, q_2, q_3\}$
- $E(q_0) = \{q_0, q_1, q_2, q_3\}$
**第二步：构造 DFA $M'$ 的状态和转移**
我们从 DFA 的初始状态开始，采用按需计算的方式，逐步构建 DFA 的状态集和转移函数。
DFA **初始状态** $s'$ = $A = E(q_0) = \{q_0, q_1, q_2, q_3\}$（非接受状态）
接着从状态 $A$ 开始，计算它对每个输入符号的转移。
- **处理状态 $A = \{q_0, q_1, q_2, q_3\}$**
- $\delta'(A, a)$ 的计算：
- NFA 目标状态：$\delta(q_1, a) \cup \delta(q_3, a) = \{q_0, q_4\} \cup \{q_4\} = \{q_0, q_4\}$
- 取 $\varepsilon$-闭包并集：$E(q_0) \cup E(q_4) = \{q_0, q_1, q_2, q_3\} \cup \{q_3, q_4\} = \mathbf{\{q_0, q_1, q_2, q_3, q_4\}}$
- 得到新状态 $B = \{q_0, q_1, q_2, q_3, q_4\}$。$B$ 包含 $q_4$，因此是接受状态。
- $\delta'(A, b)$ 的计算：
- NFA 目标状态：$\delta(q_0, b) \cup \delta(q_2, b) = \{q_2\} \cup \{q_4\} = \{q_2, q_4\}$
- 取 $\varepsilon$-闭包并集：$E(q_2) \cup E(q_4) = \{q_2\} \cup \{q_3, q_4\} = \mathbf{\{q_2, q_3, q_4\}}$
- 得到新状态 $C = \{q_2, q_3, q_4\}$。$C$ 包含 $q_4$，因此是接受状态。
- **处理状态 $B = \{q_0, q_1, q_2, q_3, q_4\}$**
- $\delta'(B, a)$ 的计算：
- NFA 目标状态：$\delta(q_1, a) \cup \delta(q_3, a) = \{q_0, q_4\} \cup \{q_4\} = \{q_0, q_4\}$
- 取 $\varepsilon$-闭包并集：$E(q_0) \cup E(q_4) = \{q_0, q_1, q_2, q_3, q_4\} = \mathbf{B}$
- 转移到自身。
- $\delta'(B, b)$ 的计算：
- NFA 目标状态：$\delta(q_0, b) \cup \delta(q_2, b) = \{q_2\} \cup \{q_4\} = \{q_2, q_4\}$
- 取 $\varepsilon$-闭包并集：$E(q_2) \cup E(q_4) = \{q_2\} \cup \{q_3, q_4\} = \mathbf{C}$
- 转移到状态 $C$。
- **处理状态 $C = \{q_2, q_3, q_4\}$**
- $\delta'(C, a)$ 的计算：
- NFA 目标状态：$\delta(q_3, a) = \{q_4\}$
- 取 $\varepsilon$-闭包并集：$E(q_4) = \mathbf{\{q_3, q_4\}}$
- 得到新状态 $D = \{q_3, q_4\}$。$D$ 包含 $q_4$，因此是接受状态。
- $\delta'(C, b)$ 的计算：
- NFA 目标状态：$\delta(q_2, b) = \{q_4\}$
- 取 $\varepsilon$-闭包并集：$E(q_4) = \mathbf{\{q_3, q_4\}}$
- 转移到状态 $D$。
- **处理状态 $D = \{q_3, q_4\}$**
- $\delta'(D, a)$ 的计算：
- NFA 目标状态：$\delta(q_3, a) = \{q_4\}$
- 取 $\varepsilon$-闭包并集：$E(q_4) = \mathbf{\{q_3, q_4\}} = \mathbf{D}$
- 转移到自身。
- $\delta'(D, b)$ 的计算：
- NFA 目标状态：$\emptyset$
- 取 $\varepsilon$-闭包并集：$\mathbf{\emptyset}$
- 得到新状态 $E = \emptyset$（死状态）。$E$ 不包含 $q_4$，因此不是接受状态。
- **处理状态 $E = \emptyset$（死状态）**
- $\delta'(E, a) = \emptyset = \mathbf{E}$
- $\delta'(E, b) = \emptyset = \mathbf{E}$
所有可达状态都已计算完毕。
第三步：最终的 DFA $M'$状态集
- **状态集 $K'$**：
$\{A, B, C, D, E\}$
- $A = \{q_0, q_1, q_2, q_3\}$
- $B = \{q_0, q_1, q_2, q_3, q_4\}$
- $C = \{q_2, q_3, q_4\}$
- $D = \{q_3, q_4\}$
- $E = \emptyset$
- **初始状态 $s'$**：$A$
- **接受状态 $F'$**：$\{B, C, D\}$, 因为含有 $q_4$。
- **转移函数 $\delta'$（表格形式）：**
| 状态 | $a$ | $b$ | 接受 |
|------|-----|-----|------|
| $A$ | $B$ | $C$ | 否 |
| $B$ | $B$ | $C$ | 是 |
| $C$ | $D$ | $D$ | 是 |
| $D$ | $D$ | $E$ | 是 |
| $E$ | $E$ | $E$ | 否 |
这样，原 NFA 被转换为等价的 DFA，所有状态和转移均已明确。
## 语言表示：正则表达式 (Regular Expressions)
正则表达式是一种用于描述语言的代数工具。其核心思想是：从**最基本的语言**（如空语言 $\emptyset$ 和单符号语言 $\{a\}$）出发，通过**三种基本运算**构造更复杂的语言。
一个正则表达式 $\alpha$ 及其表示的语言 $L(\alpha)$ 递归定义如下：
- 基础情况：
- $\emptyset$ 是正则表达式，表示空语言 $L(\emptyset) = \emptyset$
- 对于字母表 $\Sigma$ 中的每个符号 $a$，$a$ 是正则表达式，表示语言 $L(a) = \{a\}$
- 归纳步骤：若 $\alpha$ 和 $\beta$ 都是正则表达式，则
- 连接 (Concatenation)：$(\alpha\beta)$ 是正则表达式，表示语言 $L((\alpha\beta)) = L(\alpha)L(\beta)$
- 并 (Union)：$(\alpha \cup \beta)$ 是正则表达式，表示语言 $L((\alpha \cup \beta)) = L(\alpha) \cup L(\beta)$
- Kleene 星号 (Kleene Star)：$\alpha^*$ 是正则表达式，表示语言 $L(\alpha^*) = L(\alpha)^*$，即 $L(\alpha)$ 中 0 个或多个字符串的所有连接
**正则语言**的定义：所有**能够用正则表达式描述的语言**称为正则语言。
下面是一个定理: **一个语言是正则的，当且仅当它能被一台有穷自动机接受**。
这是一个“当且仅当”的命题，所以我们需要从两个方向来证明。
- 方向一：如果一个语言是正则的，那么它一定能被一台有穷自动机接受。
- 方向二：如果一个语言能被一台有穷自动机接受，那么它一定是正则的。
### 从正则表达式到有穷自动机
我们的任务是：给定任意一个正则表达式，我们都能构造出一台接受它所描述语言的有穷自动机（通常是NFA，因为更方便）。
我们的策略是递归构造。回顾正则表达式的定义：
- **基础情况**：最简单的正则表达式是 $\emptyset$（空语言）和单个符号 $a$。我们可以为每种情况分别构造一个非常简单的 NFA。
- 对于 $\emptyset$，构造一个没有接受状态的自动机。
- 对于 $a$，构造一个只有两个状态的自动机，从初始状态读入 $a$ 转移到接受状态。
- **递归步骤**：更复杂的正则表达式通过并 (Union)、连接 (Concatenation) 和 Kleene 星号 (Kleene Star) 运算组合而成。
- 如果 $L_1$ 和 $L_2$ 都能被自动机接受，则可以构造自动机分别接受 $L_1 \cup L_2$、$L_1 L_2$ 和 $L_1^*$。
- 关键在于证明：有限自动机接受的语言在这三种运算下是**封闭的**。
- **并运算**：通过新建初始状态，使用 **$\varepsilon$-转移**分别连接到两个自动机的初始状态。
- **连接运算**：将第一个自动机的所有**接受状态**通过 **$\varepsilon$-转移**连接到第二个自动机的**初始状态**，并将第二个自动机的接受状态作为整体的接受状态。
- **Kleene 星号**：新建初始状态和接受状态，允许从接受状态通过 $\varepsilon$-转移回到初始状态，同时允许直接接受空串。
- 通过递归应用上述构造方法，可以为**任意正则表达式**构造出一个**等价的 NFA**，从而证明正则表达式描述的语言都能被有限自动机接受。
### 从有穷自动机到正则表达式
现在我们来证明更难的另一个方向：**给定任意一台有限自动机（FA），如何构造出一个等价的正则表达式？**
#### **状态消除法**（State Elimination Method）
我们采用一种叫做**状态消除法**（State Elimination Method）的动态规划思想。其核心步骤如下：
1. 预处理：转换为广义有限自动机 (GFA)
- 首先，将原始自动机改造为**广义有限自动机（GFA）**。GFA 与 NFA 类似，但**转移边上的标记可以是任意正则表达式**，而不仅仅是单个符号。改造标准如下：
- 只有一个唯一的接受状态。
- 没有转移进入初始状态，也没有转移从接受状态出去。
- 通常通过增加新的初始状态和新的接受状态，并用 $\varepsilon$-转移连接它们实现。
2. 状态消除过程
- 逐步消除 GFA 的中间状态。每消除一个状态 $q$，需要修复所有经过它的路径：
- 假设有一条从 $q_i$ 到 $q_j$ 的路径，标记为 $\delta$。
- 还有一条从 $q_i$ 经过 $q$ 到 $q_j$ 的路径，$q_i \to q$ 标记为 $\alpha$，$q \to q_j$ 标记为 $\beta$，且 $q$ 上可能有自环，标记为 $\gamma$。
- 消除 $q$ 后，新增一条直接路径，其正则表达式为 $\alpha \gamma^* \beta$。
- 从 $q_i$ 到 $q_j$ 的新转移标记为原标记和新路径的并集，即 $\delta \cup \alpha \gamma^* \beta$。
- 重复此过程，直到只剩下初始状态和接受状态。
3. 最终结果: 此时，从初始状态到接受状态的**唯一转移边上的**正则表达式，就是与原始自动机等价的正则表达式。
- **初始 GFA**：将原 FA 转换为广义有限自动机（GFA），添加新的起始状态 $q_4$ 和唯一接受状态 $q_5$，并用 $\varepsilon$-转移连接。
- **消除 $q_1$**：移除 $q_1$，将所有经过 $q_1$ 的路径合并。例如，从 $q_4$ 经过 $q_1$ 到 $q_3$ 的路径合并为一条标记为 $a^*b$ 的新边；从 $q_2$ 经过 $q_1$ 到 $q_3$ 的路径合并为 $ba^*b$。
- **消除 $q_2$**：移除 $q_2$，将 $q_3$ 经过 $q_2$ 回到 $q_3$ 的路径与 $q_3$ 的自环合并，得到新的自环 $a \cup ba^*ba^*b$。
- **消除 $q_3$**：移除 $q_3$，将 $q_4$ 到 $q_3$ 的路径、$q_3$ 的自环、以及 $q_3$ 到 $q_5$ 的路径合并，得到从 $q_4$ 到 $q_5$ 的唯一路径。
- **最终正则表达式**：所有中间状态消除后，GFA 只剩下起始和接受状态，两者之间的唯一转移边标记的正则表达式即为原 FA 的等价正则表达式：$\boxed{a^*b(a \cup ba^*ba^*b)^*}$。
#### 数学归纳描述
定义 $R(i, j, k)$ 表示：从状态 $q_i$ 到 $q_j$，且所有中间状态编号不超过 $k$ 的所有路径所对应的字符串集合。
- 基础情况（Base Case, $k=0$）：$R(i, j, 0)$ 表示从 $q_i$ 到 $q_j$ 的路径，且**不经过任何中间状态**（编号 $>0$）。这只可能是一步直接转移，因此 $R(i, j, 0)$ 就是所有能直接从 $q_i$ 到 $q_j$ 的符号的集合。如果 $i = j$，还包括空串 $\varepsilon$。这个集合是有限的，可以用正则表达式（如 $a \cup b \cup c$）描述。
- 归纳步骤（Inductive Step）：假设对于所有 $i, j$，$R(i, j, k-1)$ 都可以用正则表达式描述。递推公式如下：
$$
R(i, j, k) = R(i, j, k-1) \cup R(i, k, k-1) \left(R(k, k, k-1)\right)^* R(k, j, k-1)
$$
- 公式解释：从 $q_i$ 到 $q_j$，中间状态编号不超过 $k$ 的所有路径分为两类：
1. **不经过 $q_k$ 的路径**：这些路径的中间状态编号都不超过 $k-1$，即 $R(i, j, k-1)$。
2. **经过 $q_k$ 的路径**：可以分解为三部分：
- 从 $q_i$ 到 $q_k$（中间状态不超过 $k-1$）：$R(i, k, k-1)$
- 在 $q_k$ 循环任意次（中间状态不超过 $k-1$）：$\left(R(k, k, k-1)\right)^*$
- 从 $q_k$ 到 $q_j$（中间状态不超过 $k-1$）：$R(k, j, k-1)$
由于正则表达式的三种运算（并、连接、星号）都是封闭的，且归纳假设 $R(\cdot, \cdot, k-1)$ 都是正则的，因此 $R(i, j, k)$ 也必然是正则的。
因此, 正则语言的核心理论结果是，DFA、NFA 和正则表达式在**描述语言的能力**上是完全等价的。
- **NFA 与 DFA 等价**：对于每一台非确定型有限自动机（NFA），都存在一台等价的（接受相同语言的）确定型有限自动机（DFA）。证明方法为“子集构造法”，即将 NFA 的状态集合映射为 DFA 的单个状态。
- 这意味着，NFA带来的所有便利性，都只是“表面上”的。在**计算能力的本质上**，它并没有超越DFA。
- **自动机与正则表达式等价**：一个语言是正则的（即可以用正则表达式表示）当且仅当它被一台有限自动机接受。证明思路包括：
- 从任意正则表达式构造等价的 NFA：为基础情况构造简单自动机，利用自动机在并、连接和 Kleene 星号运算下的封闭性递归组合。
- 从任意有限自动机构造等价的正则表达式：使用状态消除法，逐步移除中间状态并更新转移边的正则表达式，直到只剩下初始和接受状态。
## 正则语言与非正则语言 (Languages that are and are not regular)。
到目前为止，我们已经学习了三种强大的工具来描述和证明一个语言是正则的：
- 为它构造一台有限自动机 (FA) 。
- 为它写出一个正则表达式 。
- 利用正则语言的闭包性质 (Closure Properties)，比如并、交、补、连接和克林星号等，从已知的正则语言构造出它 。
**示例1**: 假设字母表 $\Sigma$ 是 $\{0, 1, ..., 9\}$。语言 $L$ 是所有能被 2 和 3 整除的非负整数的十进制表示（并且没有多余的前导零）。请证明 $L$ 是一个正则语言。
第一步：分解问题。我们要证明的语言 $L$ 是“能被 2 整除”的语言 $L_2$ 和“能被 3 整除”的语言 $L_3$ 的交集，即 $L = L_2 \cap L_3$。根据正则语言的闭包性质，只要 $L_2$ 和 $L_3$ 都是正则的，它们的交集 $L$ 也一定是正则的。
第二步：证明 $L_2$ 是正则的。一个数能被 2 整除，等价于它的十进制表示最后一位是 $0, 2, 4, 6, 8$。所有合法的非负整数的十进制表示组成的语言 $L_1$ 可以用正则表达式 $0 \cup [1-9][0-9]^*$ 表示（假设 $\Sigma = \{0,1,\ldots,9\}$）。$L_2$ 就是 $L_1$ 中以偶数结尾的字符串，即 $L_2 = L_1 \cap [0-9]^*[0,2,4,6,8]$。由于 $L_1$ 和 $[0-9]^*[0,2,4,6,8]$ 都是正则语言，交集 $L_2$ 也是正则的。
> $[1-9][0-9]^*$ 这一部分表示所有非零的非负整数。
> - **子部分 B1**：$[1-9]$ 是 $\{1, 2, \dots, 9\}$ 的简写，它由基本正则语言 $\{1\}, \{2\}, \dots, \{9\}$ 通过有限次并集 $\cup$ 得到。由于正则语言对并集运算封闭，$L_{B1} = \{1, 2, \dots, 9\}$ 是正则语言。
> - **子部分 B2**：$[0-9]^*$ 是 $\{0, 1, \dots, 9\}^*$ 的简写，同样是正则语言（通过有限次并集和 Kleene 星号运算）。因此 $L_{B2} = \{0, 1, \dots, 9\}^*$ 也是正则语言。
> - **连接 B1 和 B2**：部分 B 是由 $L_{B1}$（非零数字）和 $L_{B2}$（任意数字串）通过连接运算（$L_{B1}L_{B2}$）得到的。由于正则语言对连接运算封闭，$L_B = [1-9][0-9]^*$ 也是正则语言。
第三步：证明 $L_3$ 是正则的。一个数能被 3 整除，当且仅当它的各位数字之和能被 3 整除。我们可以设计一个 3 个状态的 DFA，状态分别表示“数字和模 3 余 0、1、2”。初始状态（也是接受状态）表示余 0。每读入一个数字 $d$，就从当前状态 $q$ 转移到 $((q + d) \bmod 3)$。这台 DFA 能接受所有各位数字和能被 3 整除的字符串，因此 $L_3$ 是正则语言。
第四步：结论。由于 $L_2$ 和 $L_3$ 都是正则语言，且正则语言对交集运算封闭，所以 $L = L_2 \cap L_3$ 也是正则语言。证毕。
我们再来看一个更抽象的例子来巩固闭包性质的应用。
**问题**：假设 $L'$ 是一个已知的正则语言，证明语言 $L = \{xy \mid x \in L',\ y \notin L'\}$ 也是正则的。
**证明**：
首先分析 $L$ 的结构。$L$ 中的字符串由两部分组成：第一部分 $x$ 属于 $L'$，第二部分 $y$ 不属于 $L'$。也就是说，$y$ 来自 $L'$ 的补集 $\overline{L'}$。
因此，$L$ 可以表示为 $L = L' \circ \overline{L'}$，即 $L'$ 与 $\overline{L'}$ 的连接。
根据正则语言的闭包性质：
- 正则语言对补集运算封闭，所以 $\overline{L'}$ 也是正则语言。
- 正则语言对连接运算封闭，所以 $L' \circ \overline{L'}$ 也是正则语言。
综上，$L$ 是正则语言。
下面是一些正则语言的例子：
- $L = \{a^n \mid n \ge 0\}$ 是正则的，因为它的正则表达式就是 $a^*$。
- $L = \{a^n \mid n \text{ is even}\}$ 也是正则的，对应的正则表达式为 $(aa)^*$。
- 如果 $L_0$ 是正则的，那么它的反转语言 $\{w^R \mid w \in L_0\}$ 也是正则的（正则语言对反转运算封闭）。
一个非正则语言的例子：
- $L = \{w \in \{a, b\}^* \mid w \text{ 中 } a \text{ 和 } b \text{ 的数量相等}\}$ 不是正则的。
- 为什么？可以用闭包性质和反证法证明：
- 假设 $L$ 是正则的。我们知道 $a^*b^*$ 是正则语言（正则表达式为 $a^*b^*$）。由于正则语言对交集封闭，$L \cap a^*b^*$ 也应是正则的。但 $L \cap a^*b^*$ 实际上就是 $\{a^n b^n \mid n \ge 0\}$，即所有先若干个 $a$ 再若干个 $b$，且 $a$ 和 $b$ 数量相等的字符串。我们将会证明 $\{a^n b^n \mid n \ge 0\}$ 不是正则语言，这样就产生了矛盾。因此，$L$ 不是正则的。
实际上, 非正则语言数量远大于正则语言. 下面我们从集合了的角度给予分析:
- **问题1：一个非空字母表能组成多少个字符串？**
答案是**可数无穷多**（countably infinite）。因为所有字符串都是有限长度的，可以按长度和字典序一一列举出来。
- **问题2：一个语言是可数的吗？**
是的。任何**语言都是字符串集合的子集**，所以它本身至多是可数无穷的。
- **问题3：一个非空字母表上，总共有多少种可能的语言？**
答案是**不可数无穷多**。因为所有语言的集合，是可数无穷字符串集合的幂集，而**可数集的幂集是不可数**的（其基数与实数集相同）。
- **问题4：有多少种正则语言？**
答案是**可数无穷多**。原因在于，每一个正则语言都可以用一个有限长度的字符串来描述（如正则表达式或有限自动机的描述），而所有有限字符串的集合是可数的。
**结论**：
我们有不可数无穷多种语言，但只有可数无穷多种正则语言。这意味着，绝大多数的语言都是非正则的！
为什么有些语言不是正则的呢？本质原因在于有限自动机（FA）的“有限性”：它只有有限个状态，因此**只能记住有限的信息**。
以 $\{a^n b^n\}$ 为例，判断一个字符串是否属于这个语言，需要机器在读完所有的 $a$ 后，**准确记住 $a$ 的数量**，以便后续与 $b$ 的数量进行匹配。如果 $n$ 可以任意大，这就要求机器拥有**无限的记忆能力或无限个状态**，而有限自动机无法做到这一点。
类似地，像平衡括号这样的语言，也需要无限的计数能力来确保左右括号严格匹配，这超出了有限自动机的能力范围。因此，凡是需要“**无限记忆**”或“**精确计数**”的语言，都不是正则语言。
下面列出了一些经典的、将在本章被证明为非正则的语言：
- $L_1 = \{a^n b^n \mid n \ge 0\}$
- $L_2 = \{a^n \mid n \text{ is prime}\}$
- $L_3 = \{ww^R \mid w \in \{a,b\}^*\}$（回文串）
- $L_4 = \{ww \mid w \in \{a,b\}^*\}$（重复串）
这些语言的共同点在于：它们都要求**对字符串的不同部分进行精确的数量或结构匹配**，而这种匹配超出了有限自动机（FA）**有限内存的能力范围**，因此不是正则语言。
### 泵定理 (Pumping Theorem)
直观的理解很好，但我们需要一个严格的数学工具来证明一个语言不是正则的。这个工具就是大名鼎鼎的**泵定理** (Pumping Theorem)。
一台有穷自动机 $M$ 被定义为一个五元组 $M = (K, \Sigma, \delta, s, F)$。其中，状态集合 $K$ 是一个有穷集合 (a finite set of states)。假设这台 DFA $M$ 拥有的状态总数是 $n$（即 $|K| = n$）。
现在, 我们考虑一个非常长的字符串 $w$，它的长度 $|w|$ 大于或等于状态的总数 $n$。
当 DFA $M$ 从初始状态开始，读取这个长字符串 $w$ 的前 $n$ 个符号时，它会经历 $n$ 步转移，访问 $n+1$ 个状态。
- 鸽巢（Pigeonholes）：DFA 拥有的状态总数 $n$。
- 鸽子（Pigeons）：DFA 在读取前 $n$ 个符号时，按时间顺序依次访问的 $n+1$ 个状态。
- 初始状态 $q_0$ (第 0 步)
- 第 1 个状态 $q_1$ (第 1 步)
- ...
- 第 $n$ 个状态 $q_n$ (第 $n$ 步)
根据鸽巢原理：如果有 $n+1$ 只鸽子要飞入 $n$ 个鸽巢，那么至少有一个鸽巢里必须有两只或两只以上的鸽子。这意味着：在这 $n+1$ 个被访问的状态序列中，必定有两个状态是同一个状态。
结论：环路的产生假设自动机在第 $i$ 步和第 $j$ 步（其中 $0 \le i < j \le n$）访问了同一个状态 $q$ ：$$q_i = q_j = q$$
机器在第 $i$ 步和第 $j$ 步之间读取的那段子字符串，就是导致机器从 $q$ 重新回到 $q$ 的那段路径。这段路径在状态图上表现为一个环路（loop）。
如果 $|w| \ge n$，环路必须发生在字符串前 $n$ 个符号所对应的路径中。这就是泵定理证明的第一步，通过严格的鸽巢原理，证明了对于**足够长的字符串**，**有限自动机**中必然存在一个或多个**环路**。
现在我们就可以把字符串拆分了：
- $x$ 是从开头到 $q_i$ 的部分 ($a_1 \dots a_{i-1}$)。
- $y$ 是从 $q_i$ 绕一圈回到 $q_i$ 的部分 ($a_i \dots a_j$)。
- $z$ 是剩下的部分 ($a_{j+1} \dots a_m$)。
泵定理的正式陈述：如果 L 是一个正则语言，那么必然存在一个整数 n≥1（我们称之为“**泵长度**”），使得任何在 L 中且长度不小于 n 的字符串 w，都可以被**拆分成三段** w=xyz，并且满足以下三个条件：
- $y \ne \epsilon$ (中间的“泵”部分非空)。
- $|xy| \le n$ (循环必定发生在字符串的前 $n$ 个字符以内)。
- 对于所有的 $i \ge 0$，字符串 **$xy^iz$** 仍然属于 $L$ (这就是“泵”的含义：可以泵任意次)。
#### 如何使用泵定理
泵定理是一个破坏性工具。它只能用来**证明一个语言不是正则的**，而不能用来证明一个语言是正则的。证明方法：**反证法** (Proof by contradiction)。
使用泵定理的过程，就像是在玩一个游戏。
- 对手：一个“AI”，它坚信语言 $L$ 是正则的。
- 你：一个“反方辩手”，你的目标是证明AI是错的。
- 游戏规则：
- AI先出招，它给出一个泵长度 $n$。（你不知道 $n$ 是多少，但你知道它存在）。
- 轮到你了，你必须挑选一个非常聪明的字符串 $w \in L$，且 $|w| \ge n$。
- AI再出招，它把你的 $w$ 分解成 $xyz$，但它必须遵守规则（$|xy| \le n, y \ne \epsilon$）。它会尽可能地以对它有利的方式来分解。
- 你的最后一击：你必须指出，**无论AI怎么分解**，你总能找到一个 $i$（通常是0或2），使得**泵出的新字符串 $xy^iz$ 不在语言 $L$ 中**。如果你能做到这一点，你就制造了矛盾，证明了AI的观点是错误的，因此 $L$ 不是正则的。
##### 示例: $L=\{a^ib^i \mid i \ge 0\}$ 不是正则的
我们要证明这个语言——所有由一串 $a$ 跟着一串数量完全相等的 $b$ 组成的字符串——不是正则的。严格按照泵定理的反证步骤：
1. **假设**：假设 $L$ 是正则语言。
2. **泵长度**：根据泵定理，存在一个泵长度 $n$。
3. **选择字符串**：取一个长度大于 $n$ 的字符串 $w = a^n b^n$，显然 $w \in L$ 且 $|w| = 2n \ge n$。
4. **拆分规则**：AI 必须将 $w$ 拆分为 $xyz$，满足 $|xy| \le n$ 且 $y \ne \epsilon$。
- 因为 $|xy| \le n$，所以无论怎么拆分, $x$ 和 $y$ 都只包含 $a$，$y = a^i$，其中 $i > 0$。
5. **泵操作**：选择 $i = 0$，得到新字符串 $xz = a^{n-i} b^n$。
6. **矛盾**：如果 $L$ 是正则语言, 那么根据泵定理，得到的新字符串 $xz$ 也是正则语言, 但$xz$ 中 $a$ 的数量为 $n-i < n$，$b$ 的数量为 $n$，两者不相等，因此 $xz \notin L$。
7. **结论**：存在 $i$ 使得 $xy^i z \notin L$，与泵定理矛盾。因此，$L$ 不是正则语言。
##### 证明 $L=\{a^n \mid n \text{ is prime}\}$ 不是正则的
我们采用泵定理进行反证：
1. **假设**：假设 $L$ 是正则语言。
2. **泵长度**：根据泵定理，存在一个泵长度 $n$。
3. **选择字符串**：选择一个大于 $n$ 的素数 $k$，令 $w = a^k$，显然 $w \in L$ 且 $|w| = k \ge n$。
4. **拆分规则**：AI 必须将 $w$ 拆分为 $xyz$，满足 $|xy| \le n$ 且 $y \ne \varepsilon$。由于 $w$ 全由 $a$ 组成，设 $x = a^p$, $y = a^q$, $z = a^r$，其中 $p+q \le n$, $q > 0$, $p+q+r = k$。
5. **泵操作**：根据泵定理，任意 $i \ge 0$，$xy^iz = a^{p + iq + r}$ 应属于 $L$，即 $p + iq + r$ 必须为素数。
6. **构造反例**：令 $i = k + 1$，则新字符串长度为 $p + (k + 1)q + r = (p + q + r) + kq = k + kq = k(q + 1)$。
- $k$ 是素数且 $q \ge 1$，所以 $q + 1 \ge 2$，因此 $k(q + 1)$ 是合数（大于 $k$ 且可分）。
7. **矛盾**：$a^{k(q+1)}$ 不属于 $L$，因为其长度不是素数。与泵定理要求矛盾。
**结论**：存在 $i$ 使得 $xy^iz \notin L$，因此 $L$ 不是正则语言。
### 问题：证明 $L=\{uu^Rv \mid u,v \in \{a,b\}^+\}$ 不是正则的。
这个语言 $L = \{uu^Rv \mid u, v \in \{a, b\}^+\}$ 表示一个非空回文串 $uu^R$ 后面跟着另一个非空串 $v$。直接对 $L$ 使用泵定理较难，因为 $v$ 的存在让结构复杂。我们可以先与一个精心设计的**正则语言**求**交**，得到一个**更简单但同样非正则的语言** $L'$，从而让问题转化为证明 $L'$ 不是正则的。
**第一步：与正则语言求交集**
选择正则语言 $(ab)^+(ba)^+$，与 $L$ 求交得到 $L' = L \cap (ab)^+(ba)^+ = \{(ab)^n(ba)^m \mid m > n \ge 1\}$。其中 $u = (ab)^n$，$u^R = (ba)^n$，$v = (ba)^{m-n}$，要求 $m > n$ 保证 $v$ 非空。
**第二步：对 $L'$ 使用泵定理**
假设 $L'$ 是正则语言。根据泵定理，存在泵长度 $p$。选择字符串 $w = (ab)^p(ba)^{p+1} \in L'$，满足 $|w| \ge p$。
将 $w$ 拆分为 $w = xyz$，其中 $|xy| \le p$，$y \ne \varepsilon$。由于 $|xy| \le p$，$x$ 和 $y$ 都在最前面的 $(ab)^p$ 部分。$y$ 可能是完整的 $(ab)^k$，或是部分片段（如 $a$、$ab$、$b$ 等）。
无论如何拆分 $y$，都可以选择 $i = 0$ 或 $i = 3$，使得泵出后的字符串 $xy^iz$ 不满足 $m > n$，即 $(ab)^{p+q}(ba)^{p+1}$，其中 $q$ 是泵的次数。这样得到的字符串不属于 $L'$，与泵定理矛盾。
**结论**
$L'$ 不是正则语言。由于正则语言的交集仍为正则，而 $L'$ 非正则，因此原语言 $L$ 也不是正则语言。
## 关键研究问题
1. **状态最小化目标**：给定一台 DFA，找到一台接受完全相同语言、且状态数最少的等价 DFA。Myhill-Nerode 定理为最小化提供了理论基础。它定义了一种关于字符串的等价关系 $\approx_L$（如果 $x \approx_L y$，意味着对于任何后缀 $z$，字符串 $xz$ 和 $yz$ 要么都属于 $L$，要么都不属于 $L$）。该定理证明了一个语言是正则的，当且仅当 $\approx_L$ 关系具有有穷个等价类，并且这些等价类的数量，恰好就是接受 $L$ 的最小 DFA 的状态数。最小化算法：首先移除所有从初始状态不可达的状态，然后迭代地识别并合并“等价”的状态。算法开始时，将所有状态分为两个集合：终结状态 $F$ 和非终结状态 $K-F$。在随后的每一步迭代中，检查当前同一集合中的任意两个状态 $p$ 和 $q$。如果存在任何一个输入符号 $a$，使得 $\delta(p, a)$ 和 $\delta(q, a)$ 落在上一轮迭代所划分出的不同集合中，那么 $p$ 和 $q$ 就必须被分离。重复这个细化过程，直到某轮迭代后不再有任何集合被分离为止。此时剩下的集合中的状态都是真正等价的，可以合并为最小自动机的一个状态。
2. **泵定理 (Pumping Lemma) 用途**：这不是用来证明语言是正则的，而是用来证明一个语言不是正则的。定理断言，任何正则语言 $L$ 都存在一个常数 $n$（称为“泵长度”，该值取决于接受它的 DFA 的状态数）。对于 $L$ 中任何长度至少为 $n$ 的字符串 $w$，$w$ 都可以被拆分为三部分 $w=xyz$，且满足以下所有条件：$y \ne \varepsilon$（中间部分非空），$|xy| \le n$（拆分发生在字符串的靠前部分），对于所有的 $i \ge 0$（包括 $i=0$ 时删除 $y$），字符串 $xy^iz$ 必须仍然在 $L$ 中。工作原理：如果一个 DFA 有 $n$ 个状态，它在读取一个长度为 $n$ 或更长的字符串时，根据鸽巢原理，必定至少重复访问了某一个状态。这个状态重复访问路径所对应的字符串就是 $y$。既然这是一条回路，那么这条回路可以被遍历任意多次（或 0 次），机器最终仍会到达相同的接受状态。
3. **证明语言不是正则的方法**：使用泵定理进行反证法证明。步骤如下：
- 假设目标语言 $L$ 是正则的。
- 根据泵定理，必然存在某个泵长度 $n$。
- 选择一个特定的字符串 $w \in L$，要求 $|w| \ge n$。
- 对手可以将 $w$ 拆分为 $w=xyz$，其中 $y \ne \varepsilon$ 且 $|xy| \le n$。
- 证明无论如何拆分 $w$，总能选择一个 $i$ 值（通常是 $i=0$ 或 $i=2$），使得生成的字符串 $xy^iz$ 不在 $L$ 中。
- 这导致了矛盾，因此最初的假设（$L$ 是正则的）是错误的。
经典示例：证明 $L = \{a^nb^n : n \ge 0\}$ 不是正则的。选择 $w = a^nb^n$，由于 $|xy| \le n$，$y$ 必须完全由 $a$ 组成（形如 $a^j$ 且 $j>0$）。如果选择 $i=0$，得到的字符串 $xz = a^{n-j}b^n$，a 和 b 的数量不再相等，故 $xz \notin L$，产生矛盾。
|
