Reduksi Jumlah State pada FSA

• mengurangi jumlah state dari suatu FSA dengan tidak mengurangi kemampuan menerima suatu bahasa
• Distinguishable = dapat di bedakan
• Indistinguishable = tidak dapat dibedakan

state p dan q Indistinguishable jika :

δ  (q,w) ∈ F sedang  δ  (p,w) ∈ F

atau 

δ  (q,w)  ∉  F sedang  δ  (p,w) ∉  F

untuk semua w ∈ ∑*

state p dan q Distinguishable jika :

δ  (q,w) ∈ F sedang  δ  (p,w) ∉ F

"jika p dan q Indistinguishable, dan jika q dan r juga Indistinguishable maka p dan r juga Indistinguishable dan ketiga state tersebut Indistinguishable"

Tahapan :

1. tidak ada state yang tidak tercapai dari state awal.
2. state yang distinguishable (q0,q4) ,  (q1,q4) ,  (q2,q4) ,  (q3,q4) . q0,q1,q2,q3  ∉ F sedang q4  ∈ F
3. tentukan pasangan state lainnya :

• δ  ({q0,q1} 1)  →  δ  (q0,1) = q3 ,  δ  (q1,1) = q4  →  (q3,q4)
• δ  ({q0,q2} 1)  →  δ  (q0,1) = q3 ,  δ  (q2,1) = q4  →  (q3,q4) 
• δ  ({q0,q3} 1)  →  δ  (q0,1) = q3 ,  δ  (q3,1) = q4  →  (q3,q4) 

    4. state yang distinguishable  (q0,q4) ,  (q1,q4) ,  (q2,q4) ,  (q3,q4) ,  (q0,q1) ,  (q1,q2) ,  (q0,q3)  

    5. sisanya indistinguishable   (q1,q2) ,  (q1,q3) ,  (q2,q3) 

        karena q1  indistinguishable   dengan q2 dan q2  indistinguishable dengan q3 maka 

        q1,q2,q3  indistinguishable dapat di jadikan 1 state.

Artikel Terkait: