112有穷自动机 ■确定型有穷自动机(DFA) ■非确定型有穷自动机NFA) ■带转移的NFA(2NFA)
1 11.2 有穷自动机 ◼ 确定型有穷自动机(DFA) ◼ 非确定型有穷自动机(NFA) ◼ 带ε转移的NFA(ε-NFA)
确定型有穷自动机 定义确定型有穷自动机(DFA是一个有序5元组 M=(QE,qF),其中 (1)状态集合Q:非空有穷集合 (2)输入字母表∑:非空有穷集合 (3)状态转移函数6:Qx∑→Q (4)初始状态q∈Q 控制器 (5)终结状态集FcQ n
2 确定型有穷自动机 定义 确定型有穷自动机(DFA)是一个有序5元组 M = Q,Σ,δ,q0 ,F , 其中 (1) 状态集合Q: 非空有穷集合 (2) 输入字母表Σ: 非空有穷集合 (3) 状态转移函数δ:QΣ→Q (4) 初始状态 q0Q (5) 终结状态集 FQ 控制器 a1 a2 … ai … an
DFA接受的语言 把δ扩张到Qx*上6:QX→Q,递归定义如下 Vq∈Q,a∈和w∈∑ d(, a=q δ(q,w)=0(6(q,形),a) 定义Vw∈x,如果*(qw)∈F,则称M接受 M接受的字符串的全体称作M接受的语言,记作 LM,即 L(M)={w∈|δ(q)∈F}
3 DFA接受的语言 把δ扩张到QΣ*上 δ * :QΣ*→Q, 递归定义如下 qQ, aΣ和wΣ* δ * (q,ε)=q δ * (q,wa)= δ(δ * (q,w),a) 定义 wΣ* ,如果δ * (q0 ,w)F, 则称 M接受w. M接受的字符串的全体称作M接受的语言,记作 L(M), 即 L(M)={ wΣ* | δ * (q0 ,w)F }
DFA接受的语言(续) 例1M=({91h,{a,0,9mq) 6(q0,a)=q1,o(q1,a)=q0 q1 501gn)= n为奇数 q,m为偶数 6tm,a)={9n,n为奇数 19 n为偶数 L(M={a2k+k∈N
4 DFA接受的语言(续) 例1 M= {q0 , q1 },{a}, δ,q0 ,{q1 } δ(q0 , a)=q1 , δ(q1 , a)=q0 L(M)={a 2k+1 | kN} = 为偶数 为奇数 0 1 0 q , n q , n δ (q ,a ) n = 为偶数 为奇数 1 0 1 q , n q , n δ (q ,a ) n
非确定型有穷自动机 定义非确定型有穷自动机(NFA) M=〈Q,Σ,δ,qF), 其中Q,∑,qF的定义与DFA的相同,而 6:Q×→P(Q
5 非确定型有穷自动机 定义 非确定型有穷自动机 (NFA) M =〈 Q,Σ,δ,q0 ,F 〉, 其中 Q,Σ, q0 , F 的定义与 DFA 的相同, 而 δ: Q Σ→P(Q)