在计算理论 中，确定有限状态自动机 或确定有限自动机 （英語：deterministic finite automaton, DFA ）是一个能实现状态转移的自动机 。对于一个给定的属于该自动机的状态和一个属于该自动机字母表
Σ
{\displaystyle \Sigma }
确定有限状态自动机
A
{\displaystyle {\mathcal {A}}}
一个非空有限的状态 集合
Q
{\displaystyle Q}
一个输入字母表
Σ
{\displaystyle \Sigma }
一个转移函数
δ
:
Q
×
Σ
→
Q
{\displaystyle \delta :Q\times \Sigma \rightarrow Q}
δ
(
q
,
σ
)
=
p
,
(
p
,
q
∈
Q
,
σ
∈
Σ
)
{\displaystyle \delta \left(q,\sigma \right)=p,\left(p,q\in Q,\sigma \in \Sigma \right)}
一个开始状态
s
∈
Q
{\displaystyle s\in Q}
一个接受状态的集合
F
⊆
Q
{\displaystyle F\subseteq Q}
所组成的5-元组 。因此一个DFA可以写成这样的形式：
A
=
(
Q
,
Σ
,
δ
,
s
,
F
)
{\displaystyle {\mathcal {A}}=\left(Q,\Sigma ,\delta ,s,F\right)}
确定有限状态自动机从起始状态开始，一个字符接一个字符地读入一个字符串
w
∈
Σ
∗
{\displaystyle w\in \Sigma ^{*}}
∗
{\displaystyle {}^{*}}
Kleene星号 算子。），并根据给定的转移函数一步一步地转移至下一个状态。在读完该字符串后，如果该自动机停在一个属于F的接受状态，那么它就接受该字符串，反之则拒绝该字符串。
为了在保证严谨的前提下，方便地叙述关于DFA的内容，我们定义如下扩展的转移函数：
δ
∗
:
Q
×
Σ
∗
→
Q
{\displaystyle \delta ^{*}:Q\times \Sigma ^{*}\rightarrow Q}
δ
∗
(
q
,
w
)
{\displaystyle \delta ^{*}\left(q,w\right)}
扩展转移函数递归的定义为：
δ
∗
(
q
,
ϵ
)
=
q
{\displaystyle \delta ^{*}\left(q,\epsilon \right)=q}
δ
∗
(
q
,
u
σ
)
=
δ
(
δ
∗
(
q
,
u
)
,
σ
)
,
∀
u
∈
Σ
∗
,
σ
∈
Σ
{\displaystyle \delta ^{*}\left(q,u\sigma \right)=\delta (\delta ^{*}(q,u),\sigma ),\forall u\in \Sigma ^{*},\sigma \in \Sigma }
对于一个确定有限状态自动机
A
=
(
Q
,
Σ
,
δ
,
s
,
F
)
{\displaystyle {\mathcal {A}}=\left(Q,\Sigma ,\delta ,s,F\right)}
δ
∗
(
s
,
w
)
∈
F
{\displaystyle \delta ^{*}\left(s,w\right)\in F}
被一个确定有限自动机接受的语言（或者叫“被识别的语言”）定义为：
L
(
A
)
=
{
w
∈
Σ
∗
|
A
{\displaystyle {\mathcal {L}}({\mathcal {A}})=\{w\in \Sigma ^{*}|{\mathcal {A}}~}
w
}
{\displaystyle ~w\}}
除了数学上的严谨表述，通常为了讨论方便，也使用状态图直观地表示DFA。不难发现，对于一个给定的DFA，存在唯一一个对应的有向图（但是严格意义上一个有向图不能确定出唯一一个DFA）。有向图的每个结点对应一个状态，每条有向边 对应一种转移。习惯上将结点画成两个圈表示接受状态，一个圈表示拒绝状态。用一条没有起点的边指向起始状态。
除了在表述上方便以外，在研究某些问题（如“给定的DFA的语言是否为无穷集合”）时，状态图也提供了有效的解法。
DFA是一種实际的计算模型，因为有平凡的线性时间、恒定空间的在线算法 模拟在输入流上的DFA。给定两个DFA有有效算法找到识别它们所识别语言的并集、交集和补集的DFA。还有有效算法确定一个DFA是否接受任何给定字符串，一个DFA是否接受所有字符串，两个DFA是否识别同样的语言，和对特定正则语言 找到状态数目最小的DFA（最小DFA）。
在另一方面，DFA在可识别的语言上有严格的限制—很多简单的语言，包括需要多于恒定空间来解决的任何问题，不能被DFA识别。经典的DFA不能识别的简单语言的例子是括号语言，就是由正确配对的括号组成的语言，比如 (()())。由形如an bn 的字符串组成的语言，就是有限数目个a，随后是相等数目个b。可以证明没有DFA有足够状态来识别这种语言（通俗地说，因为需要至少2n个状态，而n是不恒定的）。
能被确定有限状态自动机识别的语言是正则语言 。
确定有限状态自动机是非确定有限状态自动机 的一种极限形式。
确定有限状态自动机在计算能力上等价于非确定有限状态自动机。
没有接受状态列表并没有指定开始状态的确定有限状态机叫做转移系统 或半自动机 。 下面是一个确定有限状态自动机的例子。
A
{\displaystyle {\mathcal {A}}}
状态图 确定有限状态自动机
A
=
(
Q
,
Σ
,
δ
,
s
,
F
)
{\displaystyle {\mathcal {A}}=\left(Q,\Sigma ,\delta ,s,F\right)}
Q
=
{
S
1
,
S
2
}
{\displaystyle Q=\{S_{1},S_{2}\}}
Σ
=
{
0
,
1
}
{\displaystyle \Sigma =\{0,1\}}
s
=
S
1
{\displaystyle s=S_{1}}
F
=
{
S
1
}
{\displaystyle F=\{S_{1}\}}
δ
{\displaystyle \delta }
状态转移表 定义：对应的转移函数为：
δ
(
S
1
,
0
)
=
S
2
{\displaystyle \delta (S_{1},0)=S_{2}}
δ
(
S
1
,
1
)
=
S
1
{\displaystyle \delta (S_{1},1)=S_{1}}
δ
(
S
2
,
0
)
=
S
1
{\displaystyle \delta (S_{2},0)=S_{1}}
δ
(
S
2
,
1
)
=
S
2
{\displaystyle \delta (S_{2},1)=S_{2}}
状态
S
1
{\displaystyle S_{1}}
S
2
{\displaystyle S_{2}}
A
{\displaystyle {\mathcal {A}}}
L
(
A
)
=
{
w
|
#
0
(
w
)
≡
0
(
m
o
d
2
)
}
{\displaystyle {\mathcal {L}}({\mathcal {A}})=\{w|\#_{0}(w)\equiv 0~(mod~2)\}}
正则表达式 表示为：
(
1
∗
(
01
∗
0
)
∗
)
∗
{\displaystyle (1^{*}(01^{*}0)^{*})^{*}}
确定有限状态自动机的交，并，差，补，连接，替换，同态 ，逆同态等运算是封闭的，也就是说确定有限状态自动机通过这些运算产生的新的自动机也是确定有限状态自动机。
A
=
(
Q
,
Σ
,
δ
,
s
,
F
)
{\displaystyle {\mathcal {A}}=(Q,\Sigma ,\delta ,s,F)}
A
¯
=
(
Q
,
Σ
,
δ
,
s
,
Q
−
F
)
{\displaystyle {\bar {\mathcal {A}}}=(Q,\Sigma ,\delta ,s,Q-F)}
A
{\displaystyle {\mathcal {A}}}
A
¯
{\displaystyle {\bar {\mathcal {A}}}}
复杂度 是：
O
(
|
Q
|
)
{\displaystyle O(\left|Q\right|)}
有两个DFA，
A
1
=
(
Q
1
,
Σ
,
δ
1
,
s
1
,
F
1
)
{\displaystyle {\mathcal {A}}_{1}=(Q_{1},\Sigma ,\delta _{1},s_{1},F_{1})}
A
2
=
(
Q
2
,
Σ
,
δ
2
,
s
2
,
F
2
)
{\displaystyle {\mathcal {A}}_{2}=(Q_{2},\Sigma ,\delta _{2},s_{2},F_{2})}
B
=
(
Q
1
×
Q
2
,
Σ
,
δ
B
,
(
s
1
,
s
2
)
,
M
)
{\displaystyle {\mathcal {B}}=(Q_{1}\times Q_{2},\Sigma ,\delta _{\mathcal {B}},(s_{1},s_{2}),M)}
M
⊆
Q
1
×
Q
2
{\displaystyle M\subseteq Q_{1}\times Q_{2}}
(
s
1
,
s
2
)
{\displaystyle \left(s_{1},s_{2}\right)}
B
{\displaystyle {\mathcal {B}}}
δ
B
{\displaystyle \delta _{\mathcal {B}}}
B
{\displaystyle {\mathcal {B}}}
∀
q
1
∈
Q
1
,
q
2
∈
Q
2
,
σ
∈
Σ
:
δ
B
(
(
q
1
,
q
2
)
,
σ
)
=
(
δ
1
(
q
1
,
σ
)
,
δ
2
(
q
2
,
σ
)
)
{\displaystyle \forall q_{1}\in Q_{1},~q_{2}\in Q_{2},~\sigma \in \Sigma :\delta _{\mathcal {B}}((q_{1},q_{2}),\sigma )=(\delta _{1}(q_{1},\sigma ),\delta _{2}(q_{2},\sigma ))}
当
M
=
F
1
×
F
2
{\displaystyle M=F_{1}\times F_{2}}
B
{\displaystyle {\mathcal {B}}}
A
1
{\displaystyle {\mathcal {A}}_{1}}
A
2
{\displaystyle {\mathcal {A}}_{2}}
B
=
A
1
∩
A
2
{\displaystyle {\mathcal {B}}={\mathcal {A}}_{1}\cap {\mathcal {A}}_{2}}
A
1
{\displaystyle {\mathcal {A}}_{1}}
A
2
{\displaystyle {\mathcal {A}}_{2}}
B
{\displaystyle {\mathcal {B}}}
当
M
=
Q
1
×
F
2
⋃
F
1
×
Q
2
{\displaystyle M=Q_{1}\times F_{2}\bigcup F_{1}\times Q_{2}}
B
{\displaystyle {\mathcal {B}}}
A
1
{\displaystyle {\mathcal {A}}_{1}}
A
2
{\displaystyle {\mathcal {A}}_{2}}
B
=
A
1
∪
A
2
{\displaystyle {\mathcal {B}}={\mathcal {A}}_{1}\cup {\mathcal {A}}_{2}}
A
1
{\displaystyle {\mathcal {A}}_{1}}
A
2
{\displaystyle {\mathcal {A}}_{2}}
B
{\displaystyle {\mathcal {B}}}
交运算和并运算的复杂度都是
O
(
|
Q
1
|
|
Q
2
|
|
Σ
|
)
{\displaystyle O(\left|Q_{1}\right|\left|Q_{2}\right|\left|\Sigma \right|)}
一个同态函数
h
:
Σ
∗
→
Γ
∗
{\displaystyle h:\Sigma ^{*}\rightarrow \Gamma ^{*}}
h
(
ϵ
)
=
ϵ
{\displaystyle ~h(\epsilon )=\epsilon }
h
(
u
σ
)
=
h
(
u
)
h
(
σ
)
{\displaystyle ~h(u\sigma )=h(u)h(\sigma )}
于是则有
h
(
u
v
)
=
h
(
u
)
h
(
v
)
{\displaystyle ~h(uv)=h(u)h(v)}
ϵ
{\displaystyle ~\epsilon }
u
,
v
∈
Σ
∗
,
σ
∈
Σ
{\displaystyle ~u,v\in \Sigma ^{*},\sigma \in \Sigma }
L
⊆
Σ
∗
:
h
(
L
)
:=
{
h
(
w
)
|
w
∈
L
}
{\displaystyle {\mathcal {L}}\subseteq \Sigma ^{*}:h({\mathcal {L}}):=\{h(w)~|~w\in {\mathcal {L}}\}}
δ
(
q
,
σ
)
{\displaystyle ~\delta (q,\sigma )}
h
(
σ
)
{\displaystyle ~h(\sigma )}
L
⊆
Γ
∗
:
h
−
1
(
L
)
:=
{
w
|
h
(
w
)
∈
L
}
{\displaystyle {\mathcal {L}}\subseteq \Gamma ^{*}:h^{-1}({\mathcal {L}}):=\{w~|~h(w)\in {\mathcal {L}}\}}
Q
,
Σ
,
s
,
F
{\displaystyle ~Q,\Sigma ,s,F}
δ
′
(
q
,
σ
)
:=
δ
∗
(
q
,
h
(
σ
)
)
{\displaystyle ~\delta '(q,\sigma ):=\delta ^{*}(q,h(\sigma ))}
(
Q
,
Σ
,
δ
′
,
s
,
F
)
{\displaystyle ~(Q,\Sigma ,\delta ',s,F)}
此外替换运算和逆同态运算的方法近似。
对于一个正则语言，接受该语言的等价类 自动机是一个
(
Q
,
Σ
,
δ
,
s
,
F
)
{\displaystyle ~(Q,\Sigma ,\delta ,s,F)}
Q是等价关系 ~L 的等价类的集合：
[
x
]
,
x
∈
Σ
∗
{\displaystyle [x],x\in \Sigma ^{*}}
s
=
[
ϵ
]
{\displaystyle ~s=[\epsilon ]}
F
=
{
[
x
]
|
x
∈
L
}
{\displaystyle F=\{[x]~|~x\in L\}}
δ
(
[
x
]
,
σ
)
=
[
x
σ
]
{\displaystyle ~\delta ([x],\sigma )=[x\sigma ]}
~L 被称为Nerode关系，是Myhill-Nerode定理 的基础。简单的来说就是对于任意
x
,
y
,
z
∈
Σ
∗
{\displaystyle ~x,y,z\in \Sigma ^{*}}
x
z
∈
L
⇔
y
z
∈
L
{\displaystyle xz\in L\Leftrightarrow yz\in L}
L y。
对于任意给定的确定有限状态自动机都能找到一个与之计算能力等价的最小确定有限状态自动机，简称最小自动机。该最小自动机中状态的数量等于能识别相同语言的等价类自动机中等价关系的数量，我们可以称最小自动机和等价类自动机“实际上”是相等的，也就是同构 。非正式的说法是：对于最小自动机上的任意状态都可以通过一个同构函数变换成等价类自动机上的一个状态。
能识别一个正则语言的等价类自动机是唯一的，因此能识别该语言的最小自动机也是唯一的。
定义一个非等价关系：
N
:=
{
(
p
,
q
)
|
p
,
q
∈
Q
,
∃
w
∈
Σ
∗
:
δ
∗
(
p
,
w
)
∈
F
↔
δ
∗
(
q
,
w
)
∉
F
}
{\displaystyle N:=\{(p,q)~|~p,q\in Q,\exists w\in \Sigma ^{*}:\delta ^{*}(p,w)\in F\leftrightarrow \delta ^{*}(q,w)\notin F\}}
如果
p
∈
F
,
q
∉
F
{\displaystyle p\in F,~q\notin F}
重复步骤3，直到所标记的状态对没有变化为止
对于未标记的状态对(p,q)和σ，如果
(
δ
(
p
,
σ
)
,
δ
(
q
,
σ
)
)
{\displaystyle ~(\delta (p,\sigma ),\delta (q,\sigma ))}
以上所有标记了的状态对的集合就是非等价关系N 以下是由一个任意DFA转换到一个最小DFA的步骤：
把所有不能从开始状态达到的状态删除
通过上述标记算法计算非等价关系N
一步一步将不属于N的状态对中的两个状态合成一个状态 这样就得到了接受相同语言的最小自动机。复杂度为
O
(
|
Q
|
2
|
Σ
|
)
{\displaystyle O(\left|Q\right|^{2}\left|\Sigma \right|)}
Michael Sipser, Introduction to the Theory of Computation . PWS, Boston. 1997. ISBN 0-534-94728-X . Section 1.1: Finite Automata, pp.31–47. Subsection "Decidable Problems Concerning Regular Languages" of section 4.1: Decidable Languages, pp.152–155.4.4 DFA can accept only regular language
每个语言范畴都是其直接上面的范畴的真子集 每个语言范畴内的语言都可以用同一行的文法和自动机表示
![{\displaystyle [x],x\in \Sigma ^{*}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a7ad8b871875e984fd22a788ac743393c351e69f)
![{\displaystyle ~s=[\epsilon ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0f1f45cd2b75ab8c69089dbc390f846496c8c92f)
![{\displaystyle F=\{[x]~|~x\in L\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0bd5493a6dee95fe4cd9269dff9f370ebf63d396)
![{\displaystyle ~\delta ([x],\sigma )=[x\sigma ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0c22c23e9fa723da9837bcefb6218a1646b3b9a3)
