有限自动机是一种识别装置的抽象概念，它能准确识别正规集。有限自动机分为确定的有限自动机（Deterministic Finite Automate, DFA）和不确定的有穷自动机（Nondeterministic Finite Automate, NFA）两类，以下将用DFA和NFA指代，不再赘述。
区别：在某种状态下，面临一个特定的符号时存在不止一个转换，即允许进入多于一个的状态集合。
格式：<S, Σ，T, s0, F>， 其中
S表示非空的有限状态集Σ是非空的输入字母表T是转移函数（在NFA中结果是一个状态的集合）s0是唯一的起始状态F∈S，是非空的终结状态直接从正规式构造DFA的算法比较复杂，因此引入构造起来相对简单的NFA来间接完成构造DFA的目的。
从NFA构造出等价的DFA的步骤 1）消除空转移 2）确定化每个多重转移状态子集I的 ε \varepsilon ε_闭包：状态子集I的 ε \varepsilon ε_闭包，就是从I中的任何一个状态经过任意个 ε \varepsilon ε连线 ε \varepsilon ε所能达到的所有状态。
leftrightε_CLOSURE{{0}} = {0}将{0}定义为初态q0ε_CLOSURE{q0, a} = {1, 2, 4}将{1, 2, 4}记为q1ε_CLOSURE{q0, b} = {}标记q0ε_CLOSURE{q1, a} = {5}将{5}记为q2(终态)ε_CLOSURE{q1, b} = {2, 3, 4}将{2, 3, 4}记为q3。标记q1ε_CLOSURE{q2, a} = {}NULLε_CLOSURE{q2, b} = {}标记q2ε_CLOSURE{q3, a} = {5}即q2ε_CLOSURE{q3, b} = {2, 3, 4}即q3到此算法结束，转化后DFA示意图如下所示 从NFA转化得到的DFA不一定是最优的，可以通过合并等价状态将DFA最小化。
对于有限自动机中的任意两个状态t和s，若从其中一个状态出发接受输入字符串ω，而从另一状态出发不接受ω，或者从t和s出发到达不同的接受状态，则称ω对状态s和t是可区分的。若状态s和t不可区分，则称其为可以合并的等价状态。
由于q1和q3是不可区分的，因此可以做等价变换将DFA做最小化处理。处理结果如下：
