自动机理论研究抽象计算装置或“机器”，因为某个叫后缀自动机的东西和编译原理，就来康康这是啥。
一些贯穿自动机理论的概念
字母表
“字母表”是符号的有穷非空集合， 通常使用$\Sigma$表示。
例如：
- $\Sigma$ = {0, 1}, 二进制字母表。
- $\Sigma$ = {a, b, …, z}, 所有小写字母集合。
串
“串”（或者单词）是从某个字母表中选择符号的有穷序列。
例如：010101是从$\Sigma$ = {0, 1} 中选出的串。
- 空串：是出现0次符号的串，记作$\varepsilon$。它是可以从任何字母表中选择的串。
- 串的长度：定义$\Sigma^k$是长度为$k$的串的集合，标准记号为$|w|$，$|\varepsilon|=0$ 。
- 字母表的幂：定义$\Sigma^k$为长度为$k$的串的集合，串的每个符号都属于$\Sigma$ 。字母表的所有串的集合约定记为$\Sigma^*$ 。
语言
$\Sigma$是某个具体的字母表，全都从$\Sigma^*$中选出的串的一个集合称为“语言”。如果$\Sigma$是字母表，且$L\subseteq\Sigma^*$，则$L$是$\Sigma$上的语言。
问题
一个“问题”就是判定一个给定的串是否属于某个具体语言的提问。
如果$\Sigma$是字母表，$L$是$\Sigma$上的语言，则问题$L$就是：给定$\Sigma^*$中的一个串$w$，判定$w$是否属于$L$。
因此，任何口头上称为“问题”的东西，都可以表示为语言的成员性。
确定型有穷自动机与非确定型有穷自动机的定义
一个确定型有穷自动机包括：
- 一个有穷的状态集合，通常记作$Q$。
- 一个有穷的“输入符号”集合，通常记作$\Sigma$。
- 一个转移函数， 以一个状态和输入符号作为变量，返回一个状态。转移函数通常记作$\delta$。在非形式化代表自动机的途中，用状态之间的箭弧和箭弧上的标记来表示$\delta$。如果$q$是一个状态，$a$是一个输入符号，则$\delta(q,a)$是这样的状态$p$，使得从$p$到$q$有带$a$标记的箭弧。
- 一个初始状态，是$Q$中状态之一。
- 一个终结状态活接受状态的集合$F$。集合$F$是$Q$的子集。
通常用缩写DFA来指示确定型有穷自动机。通常用五元组记号来讨论DFA： \(A=(Q,\Sigma,\delta,q_0,F)\) 对于非确定型有穷自动机（NFA），实质上像DFA那样来表示NFA： \(A=(Q,\Sigma,\delta,q_0,F)\) NFA与DFA唯一的区别在于$\delta$的返回类型。在NFA的情况下，返回值是一个状态集合；在DFA的情况下，返回值是单个状态。
因此，我们可以通过“子集构造”的方法，证明DFA能做NFA所做的一切。