確定有窮自動機：（DFA）D是一個五元組：D=（K，Σ，M，S，F）其中
K：有窮非空的狀態集合；
Σ：有窮非空的輸入符號字母表；
M：轉換函式，是在K×Σ→K上的映像，即，如 M(ki,a)=kj,(ki∈K,kj∈K)就意味著，當前狀態為ki，輸入符為a時，將轉換為下一個狀態kj，我們把kj稱作ki的一個後繼狀態；
S∈K是唯一的一個初態；
F K是非空的終態集合。
基本介紹
- 中文名：確定有窮自動機
- 外文名：Determine the finite automaton
- 對象：有窮非空的狀態集合
- 實質：有窮非空的輸入符號字母表
基本概念,實例解析,
基本概念
實例解析
DFAM=（{S,U,V,Q},{a，b}，f，S，{Q}）其中f定義為：
f (S, a) = U f ( V, a ) = U
f (S, b) = V f ( V, b ) = Q
f (U, a) = Q f ( Q, a ) = Q
f (U, b) =V f ( Q, b) = Q
一個DFA可以表示成一個狀態圖（或稱狀態轉換圖）。 假定DFA有m個狀態，n個輸入字元，那么這個狀態圖含有m個結點，每個結點最多有n個弧射出，整個圖含有惟一一個初態結點和若干個終態結點，初態結點冠以“”或標以“—”，終態結點用雙圈表示或標以“+”，若f (ki, a) =kj，則從狀態結點ki到狀態結點kj，畫標記為a的弧。
