有限自动机( Finite automata) 描述程序设计语言中的单词的识别过程。 主要内容: ●确定有限自动机DFA( deterministic Fa 确定有限自动机DFA的实现 非确定有限自动机NFA( Nondeterministic fa ●NFA到DFA的转换 ●DFA的化简
有限自动机(Finite Automata) 描述程序设计语言中的单词的识别过程。 主要内容： ⚫ 确定有限自动机DFA(Deterninistic FA) ⚫ 确定有限自动机DFA的实现 ⚫ 非确定有限自动机NFA(Nondeterninistic FA) ⚫ NFA到DFA的转换 ⚫ DFA的化简
确定有限自动机DFA 确定有限自动机DA为一个五元组 (Σ,Ss,S,f,TS),其中 ●∑是一个有穷字母表,它的每个元素称为一个 输入字符; SS是一个有穷集,它的每个元素称为一个状态; ●S∈SS是唯一的一个初始状态; f是在Ss×∑>SS上的转换函数 ● TScSS,是一个终止状态集,又称为接受状态 集
确定有限自动机DFA ⚫ 确定有限自动机DFA为一个五元组 (,SS,S0,f,TS)，其中： ⚫ 是一个有穷字母表，它的每个元素称为一个 输入字符； ⚫ SS是一个有穷集，它的每个元素称为一个状态； ⚫ S0 SS是唯一的一个初始状态； ⚫ f是在 SS → SS上的转换函数 ⚫ TSSS，是一个终止状态集，又称为接受状态 集
DFA的两种表示方式 状态转换图 结点表示状态,转换边表示转换函数,边 的箭头方向指向转换函数中定义的转换方 向。标识出初始状态和终止状态。 状态转换表: 可用二维数组描述。标识出初始状态和终 止状态 Trans (S,, a)=s
DFA的两种表示方式 ⚫ 状态转换图： 结点表示状态，转换边表示转换函数，边 的箭头方向指向转换函数中定义的转换方 向。标识出初始状态和终止状态。 ⚫ 状态转换表： 可用二维数组描述。标识出初始状态和终 止状态。 Trans（ SI ，a）＝ SJ
个DFA的例子 DFA M=(a, b, S,U,,Q, S,f( Q) 其中f定义为: f(s,a=U f(v,a=U f(S,b)=Ⅴ f(V,b=Q f(U, a=Q f(Q, a=Q f(U, b=v f(Q, b=Q
一个DFA的例子 ⚫ DFA M=( {a,b}, {S,U,V,Q}, S, f, {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
状态转换图
S U V Q a b b a b a a,b 状态转换图