确定的有限自动机: Deterministic Finite Automata,简称DFA。 一个确定的有限自动机是个五元组: (S,∑,f,s0, Z),其中:
(1)S是一个有限集合,它的每个元素称为一个状态。
(2)∑是一个有穷字母表,它的每个元素称为一个输入字符。
(3)f是SX∑ →S上的单值部分映像。f(A, a)=Q表示当前状态为A、输入为a时,将转换到下一状态Q。称Q为A的一个后继状态。
(4) s0 ∈S,是唯一的一个开始状态。
(5)Z是非空的终止状态集合,Z⊆S。
状态转换图:简称为转换图,是一个有向图。DFA中的每个状态对应转换图中的一个结点,DFA中的每个转换函数对应图中的一条有向弧,若转换函数为f(A,a)=Q,则该有向弧从结点A出发,进入结点Q,字符a是弧上的标记。
状态转换矩阵:就是用一个二维数组表示确定的有限自动机。
例如:确定的有限自动机M1= ({s0,s1,s2,s3}, {a,b},f,s0,{s3}),其中f为:f(s0,a)=s1,f(s0,b)= s2 , f(s1,a)= s3 , f(s1,b)= s2 , f(s2,a)= s1 , f(s2,b)= s3 , f(s3,a)= s3;