DFA

定义: 有穷自动机是一个5元组 $(Q, Σ, δ, q_0, F)$ , 其中
1) $Q$是一个有穷集合, 叫做状态集.
2) $Σ$是一个有穷集合, 叫做字母表.
3) $δ: Q×Σ→Q$ 是转移函数.
4) $q_0∈Q$是起始状态.
5) $F \subseteq Q$是接受状态集

在算数中,基本对象是数,工具是处理数的运算,如加减乘除. 在计算理论中,对象是语言,工具包括为处理语言所设计的运算.设$A$是机器$M$接受的全部字符串集, 称$A$是机器$M$的语言,记做$L(M)=A$.定义如下三种运算,称作正则运算.

定义:设$A和B$是两个语言

并: $A \cup B=\{ x| x \in A \text{ 或 } x \in{B}\}$
连结: $A \circ B=\{ xy | x \in{A} \text{ 且 } y\in{B}\}$
闭包: $A \text{*}= \{ x_1x_2\dotsb x_k|k \geq 0 \text{ 且 } \forall{x_i}\in A\} $

并运算把$A和B$中的所有字符串合并在一个语言中.
连结运算以所有可能的方式,把$A$中的一个字符串接在$B$中的一个字符串前面,得到新的语言中的全部字符串.
闭包运算是一个一元运算,他把$A$中任意个字符串连结在一起得到新语言中的一个字符串.以为任意个包括0个,所以空串 $\epsilon$总是$A \text{*}$的一个成员.

$\epsilon$-NFA

非确定型有穷自动机是一个5元组 $(Q, Σ, δ, q_0, F)$ , 其中
1) $Q$是一个有穷集合, 叫做状态集.
2) $Σ$是一个有穷集合, 叫做字母表.
3) $δ: Q×(Σ\cup\{\epsilon\})→2^Q$ 是转移函数.
4) $q_0∈Q$是起始状态.
5) $F \subseteq Q$是接受状态集

与DFA不同之处在于
1) 状态转移的结果为状态集合的幂集. (定义:一个集合$Q$的所有子集所组成的集合称作集合$Q$的幂集记做$2^Q$,其中包括全集和空集.)
2) 允许空串状态转移($\epsilon\text{-move}$)