①先構造相應的NFA轉移圖及轉移表
| 1 | ||
|---|---|---|
| → q 0 \rightarrow q _0 →q0 | { q 0 } \{q_0\} {q0} | { q 0 , q 1 } \{q_0,q_1\} {q0,q1} |
| q 1 q_1 q1 | { q 2 } \{q_2\} {q2} | { q 2 } \{q_2\} {q2} |
| q 2 q_2 q2 | { q 3 } \{q_3\} {q3} | { q 3 } \{q_3\} {q3} |
| q 3 q_3 q3 | { q 4 } \{q_4\} {q4} | { q 4 } \{q_4\} {q4} |
| q 4 q_4 q4 | { q 5 } \{q_5\} {q5} | { q 5 } \{q_5\} {q5} |
| q 5 q_5 q5 | { q 6 } \{q_6\} {q6} | { q 6 } \{q_6\} {q6} |
| q 6 q_6 q6 | { q 7 } \{q_7\} {q7} | { q 7 } \{q_7\} {q7} |
| q 7 q_7 q7 | { q 8 } \{q_8\} {q8} | { q 8 } \{q_8\} {q8} |
| q 8 q _8 q8 | { q 9 } \{q_9\} {q9} | { q 9 } \{q_9\} {q9} |
| q 9 q_9 q9 | { q 10 } \{q_{10}\} {q10} | { q 10 } \{q_{10}\} {q10} |
| ∗ q 10 * q_{10} ∗q10 | { } \{\} {} | { } \{\} {} |
可 知 該 N F A 為 N = ( Q , Σ , δ , q 0 , F ) , 可知該NFA為N=(Q ,\Sigma,\delta,q _0,F), 可知該NFA為N=(Q,Σ,δ,q0,F),
Q = { q 0 , q 1 , … , q 10 } , Σ = { 0 , 1 } , F = { q 10 } Q=\{q_0,q_1,\dots ,q_{10}\},\Sigma=\{0,1\},F=\{q_{10}\} Q={q0,q1,…,q10},Σ={0,1},F={q10}
{ δ ( q 0 , 0 ) = { q 0 } , δ ( q 0 , 1 ) = { q 0 , q 1 } δ ( q i , 0 ) = δ ( q i , 1 ) = { q i + 1 } , 1 ≤ i ≤ 9 δ ( q 10 , 0 ) = δ ( q 10 , 1 ) = Φ \begin{cases} \delta(q_0,0)=\{q_0\},\delta(q_0,1)=\{q_0,q_1\} \\ \delta(q_i,0)=\delta(q_i,1)=\{q_{i+1}\},1 \leq i \leq 9 \\ \delta(q_{10},0)=\delta(q_{10},1)=\Phi \end{cases} ⎩⎪⎨⎪⎧δ(q0,0)={q0},δ(q0,1)={q0,q1}δ(qi,0)=δ(qi,1)={qi+1},1≤i≤9δ(q10,0)=δ(q10,1)=Φ
②将NFA轉化為DFA
| 1 | ||
|---|---|---|
| → { q 0 } \rightarrow \{q _0 \} →{q0} | { q 0 } \{ q_0 \} {q0} | { q 0 , q 1 } \{q_0,q_1\} {q0,q1} |
| { q 0 , q 1 } \{q_0,q_1\} {q0,q1} | { q 0 , q 2 } \{ q_0,q _2 \} {q0,q2} | { q 0 , q 1 , q 2 } \{q_0,q_1,q_2\} {q0,q1,q2} |
| { q 0 , q 2 } \{ q_0,q _2 \} {q0,q2} | { q 0 , q 3 } \{ q_0,q _3 \} {q0,q3} | { q 0 , q 1 , q 3 } \{q_0,q_1,q_3\} {q0,q1,q3} |
| { q 0 , q 1 , q 2 } \{q_0,q_1,q_2\} {q0,q1,q2} | { q 0 , q 2 , q 3 } \{ q_0,q _2,q _3 \} {q0,q2,q3} | { q 0 , q 1 , q 2 , q 3 } \{q_0,q_1,q_2,q_3\} {q0,q1,q2,q3} |
| { q 0 , q 3 } \{ q_0,q _3 \} {q0,q3} | { q 0 , q 4 } \{ q_0,q _4 \} {q0,q4} | { q 0 , q 1 , q 4 } \{q_0,q_1,q_4\} {q0,q1,q4} |
| { q 0 , q 1 , q 3 } \{q_0,q_1,q_3\} {q0,q1,q3} | { q 0 , q 2 , q 4 } \{ q_0,q _2,q _4 \} {q0,q2,q4} | { q 0 , q 1 , q 2 , q 4 } \{q_0,q_1,q_2,q_4 \} {q0,q1,q2,q4} |
| { q 0 , q 2 , q 3 } \{ q_0,q _2,q _3 \} {q0,q2,q3} | ⋯ \cdots ⋯ | ⋯ \cdots ⋯ |
| { q 0 , q 1 , q 2 , q 3 } \{q_0,q_1,q_2,q_3\} {q0,q1,q2,q3} | ⋯ \cdots ⋯ | ⋯ \cdots ⋯ |
| { q 0 , q 4 } \{ q_0,q _4 \} {q0,q4} | ⋯ \cdots ⋯ | ⋯ \cdots ⋯ |
| { q 0 , q 1 , q 4 } \{q_0,q_1,q_4\} {q0,q1,q4} | ⋯ \cdots ⋯ | ⋯ \cdots ⋯ |
| { q 0 , q 2 , q 4 } \{ q_0,q _2,q _4 \} {q0,q2,q4} | ⋯ \cdots ⋯ | ⋯ \cdots ⋯ |
| { q 0 , q 1 , q 2 , q 4 } \{q_0,q_1,q_2,q_4 \} {q0,q1,q2,q4} | ⋯ \cdots ⋯ | ⋯ \cdots ⋯ |
| ⋮ \vdots ⋮ | ⋯ \cdots ⋯ | ⋯ \cdots ⋯ |
| ⋮ \vdots ⋮ | ⋯ \cdots ⋯ | ⋯ \cdots ⋯ |
| { q 0 , q 1 , q 2 , ⋯ , q 10 } \{q_0,q_1,q_2,\cdots,q_{10}\} {q0,q1,q2,⋯,q10} | { q 0 , q 2 , q 3 , ⋯ , q 10 } \{q_0,q_2,q_3,\cdots,q_{10}\} {q0,q2,q3,⋯,q10} | { q 0 , q 1 , q 2 , ⋯ , q 10 } \{q_0,q_1,q_2,\cdots,q_{10}\} {q0,q1,q2,⋯,q10} |
分 析 得 知 該 D F A 狀 态 有 2 10 個 ， 數 量 太 多 ， 不 适 合 畫 轉 移 圖 或 轉 移 表 ， 因 此 用 形 式 化 定 義 描 述 該 D F A ， 設 該 N F A 對 應 的 D F A 為 D = ( Q D , Σ , δ D , { q 0 } , F D ) 分析得知該DFA狀态有2^{10}個，數量太多，不适合畫轉移圖或轉移表，是以用形式化定義描述該DFA，設該NFA對應的DFA為D=(Q _D,\Sigma,\delta _D,\{q _0\},F_D) 分析得知該DFA狀态有210個，數量太多，不适合畫轉移圖或轉移表，是以用形式化定義描述該DFA，設該NFA對應的DFA為D=(QD,Σ,δD,{q0},FD)
由 歸 納 法 可 知 由歸納法可知 由歸納法可知
Q D = { q 0 ∪ p ∣ p ∈ P ( { q 1 , q 2 , ⋯ , q 10 } ) } , P ( { q 1 , q 2 , ⋯ , q 10 } ) 是 { q 1 , q 2 , ⋯ , q 10 } 的 幂 集 Q_D=\{ q_0 \cup p | p \in P(\{q_1,q_2,\cdots,q_{10}\})\},\quad P(\{q_1,q_2,\cdots,q_{10}\})是\{q_1,q_2,\cdots,q_{10}\}的幂集 QD={q0∪p∣p∈P({q1,q2,⋯,q10})},P({q1,q2,⋯,q10})是{q1,q2,⋯,q10}的幂集
設 q D = { q 0 , q a , q b , ⋯ , q n } , 其 中 0 < a < b < ⋯ < n ≤ 10 , 對 所 有 q D ∈ Q D , 設q_D=\{q_0,q_a,q_b,\cdots,q_n\},其中0<a<b<\cdots<n\leq10,對所有q _D \in Q_D, 設qD={q0,qa,qb,⋯,qn},其中0<a<b<⋯<n≤10,對所有qD∈QD,
δ D ( q D , 0 ) = { q 0 , q a + 1 , q b + 1 , ⋯ , q min ( n + 1 , 10 ) } \delta _D(q_D,0)=\{q_0,q_{a+1},q_{b+1},\cdots,q_{\min(n+1,10)}\} δD(qD,0)={q0,qa+1,qb+1,⋯,qmin(n+1,10)}
δ D ( q D , 1 ) = { q 0 , q 1 , q a + 1 , q b + 1 , ⋯ , q min ( n + 1 , 10 ) } \delta _D(q_D,1)=\{q_0,q_1,q_{a+1},q_{b+1},\cdots,q_{\min(n+1,10)}\} δD(qD,1)={q0,q1,qa+1,qb+1,⋯,qmin(n+1,10)}
F D = { f D ∣ f D ∩ { q 10 } ≠ Φ , f D ∈ Q D } F_D=\{ f_D | f_D \cap \{q_{10}\} \neq \Phi,f_D \in Q_D \} FD={fD∣fD∩{q10}=Φ,fD∈QD}
F D = { f D ∣ f D ∩ { q 10 } ≠ Φ , f D ∈ Q D } F_D=\{ f_D | f_D \cap \{q_{10}\} \neq \Phi,f_D \in Q_D \} FD={fD∣fD∩{q10}=Φ,fD∈QD}
![近世代數--環同态--環的擴張定理[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)