有限自动机

DFA(确定有限自动机)

一个确定有限自动机M是一个5元组 M={S,∑,f,S0,Z}
S: 是一个有限状态集，它的每一个元素称为一个状态；
∑: 是一个有穷字母表，它的每一个元素称为一个输入符号；
f: 是转换函数，定义了从上的一个单值映射，即，指明当前的状态为p，当输入符号为a时，则转换到下一个状态q，q称为p的后继状态；
S0: 是一个唯一的初始状态；S0∈S
Z: 是一个终止状态集。

有限自动机

NFA(不确定有限自动机)

一个不确定有限自动机M是一个5元组 M={S,∑,f,S0,Z}
S: 是一个有限状态集，它的每一个元素称为一个状态；
∑: 是一个有穷字母表，它的每一个元素称为一个输入符号；
f: 是转换函数，定义了从上的一个单值映射，即，指明当前的状态为p，当输入符号为a时，则转换到下一个状态q，q称为p的后继状态；
S0: 是一个非空状态集；S0属于S
Z: 是一个终止状态集。

NFA转DFA

有限自动机
ε:输入空

有限自动机

求T1
{1,3,4,5,Z} 输入0 分析:
1输入0 后 T1={1,3}
然后 3输入0 T1={1,3,4,5,Z}
然后 4输入0 T1={1,3,4,5,Z}
然后5输入0 T1={1,3,4,5,Z,6}
然后z输入0 T1={1,3,4,5,Z,6}
求T2:
首先求T3： {1,3,4,5,Z}输入1 T3={}