基本概念

实例解析

基本概念

确定有穷自动机：（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是非空的终态集合。

实例解析

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的弧。