确定有限状态自动机
在计算理论中，确定有限状态自动机或确定有限自动机（英语：deterministic finite automaton, DFA）是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表
的字符，它都能根据事先给定的转移函数转移到下一个状态（这个状态可以是先前那个状态）。
基础概念
定义
确定有限状态自动机
是由
一个非空有限的状态集合
一个输入字母表
（非空有限的字符集合）
一个转移函数
（例如：
）
一个开始状态
一个接受状态的集合
所组成的5-元组。因此一个DFA可以写成这样的形式：
。
工作方式(非正式的语义)
确定有限状态自动机从起始状态开始，一个字符接一个字符地读入一个字符串
（这里的
指示Kleene星号算子。），并根据给定的转移函数一步一步地转移至下一个状态。在读完该字符串后，如果该自动机停在一个属于F的接受状态，那么它就接受该字符串，反之则拒绝该字符串。
扩展转移函数
为了在保证严谨的前提下，方便地叙述关于DFA的内容，我们定义如下扩展的转移函数：
。
是自动机从状态q顺序读入字符串w后达到的状态
扩展转移函数递归的定义为：
