有限自动机和正则表达式

有限自动机

确定有限自动机（Deterministic Finite Automaton，DFA）包含如下部分
- $\Sigma$ 为字母表
- $Q$ 为状态集， $q_0 \in Q$ 为初态， $F \subset Q$ 为终态的集合
- $\delta: Q \times \Sigma \to Q$ 为转移映射
$M$ 的语言为
$L(M) = \{ w : M \text{ accepts } w \},$
其中， $M$ 接受的字符串 $w = (w_1, \ldots, w_n)$ 为从初态到终态经过的字符串，
$\xymatrix@C=1.4em{q_0 \ar[r]^-{w_1} & q_1 \ar[r]^-{w_2} & \ldots \ar[r]^-{w_{n - 1}} & q_{n - 1} \ar[r]^-{w_n} & q_n \in F}.$
非确定有限自动机（Nondeterministic Finite Automaton，NFA）

正则表达式可以由正则运算生成。设、为字符集
- （并集） $A \cup B$
- （乘积） $A \times B$
- （自由幺半群） $\cup_{n = 0}^\infty A^n$
在编程语言中，我们通常使用如下记号
- 并集即选择，比如 $[a|b] = \{ a, b \}$
- 乘积即联结，比如 $ab$
- 自由幺半群即0次或者以上，比如 $a* = \{ \emptyset, a, aa, \ldots \}$
- 1次或者以上，比如 $a+ = aa* = \{ a, aa, \ldots \}$
- 0次或者1次，比如 $a? = [\emptyset|a] = \{ \emptyset, a \}$