在計算理論 中，確定有限狀態自動機 或確定有限自動機 （英語：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)
