自动机与正则语言
引入
词汇
| English | 释义 | 拼音 |
|---|---|---|
| deterministic finite automaton | 确定有限自动机 | què dìng yǒu xiàn zì dòng jī |
| pumping lemma | 泵引理 | bèng yǐn lǐ |
表格机器
- 确定有限自动机 deterministic finite automaton（DFA）是状态加转移表：读一个符号、走一步、输入结束才判接受。课程 DFA 接受 $\{a, b\}$ 上以 $ab$ 结尾的串。
{exercise:uni-cs1101-dfa}
练习
课程 DFA 读 aba 止于状态——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
q0-a-q1、q1-b-q2、q2-a-q1：止于 q1，被拒（接受态是 q2）。
泵上限
- 泵引理 pumping lemma：足够长的接受串可拆 $xyz$，满足 $|xy| \le p$、$|y| \ge 1$，且每个 $xy^iz$ 都被接受——所以 $L = \{a^n b^n\}$ 不是正则：泵 $y$（全是 $a$）计数就破。
- 正则语言无法无界计数——无记忆就是天花板。
{exercise:uni-cs1101-pumping}
练习
泵引理表明 a^n b^n 非正则，因为——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
y 落在 a 段；泵动只改 a 的计数而不改 b。
精确轨迹
aabab走 q0→q1、q1→q1、q1→q2、q2→q1、q1→q2——接受。aba走 q0、q1、q2、q1——拒绝（停在半路）。- 正则
ab|ba的 NFA 猜分支；子集构造的 DFA 同时跟踪两种可能——确定化可能让状态数翻方。
{exercise:uni-cs1101-trace}
练习
ends-in-ab DFA 上 aabab 的轨迹是——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
a:q1、a:q1、b:q2、a:q1、b:q2——接受。