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.

Non-deterministic Finite Automata (NFA)

• dari suatu state bisa terdapat 0.1 atau lebih transisi berlabel input yang sama.
• fungsi transisi = setiap pasang state-input bisa memiliki 0 (nol) atau lebih pilihan untuk state berikutnya.

δ (q0,a) = {q0,q1}

 input string 'ab' maka : δ (q0,ab) = (q1,b)

                                                   = q1  → diterima 

 input string 'ab' maka : δ (q0,ab) = (q0,b)

                                                   = q1  → diterima 

δ (q1,b) = Ø

Deterministic Finite Automata (DFA)

• Dari suatu state ada tepat satu state berikutnya untuk simbol input yang diterima

Q = {q0,q1,q2}
∑  = {a,b}
S =  q0
F = {q2}

fungsi transisi :
δ (q0,a) = q0
δ (q0,b) = q1
δ (q1,a) = q1
δ (q1,b) = q2
δ (q2,a) = q1
δ (q2,b) = q2

input string 'abb' maka : δ (q0,abb) = (q0,bb)

                                                      = (q1,b)

                                                      = q2  → diterima 

input string 'baba' maka : δ (q0,baba) = (q1,aba)

                                                          = (q1,ba)

                                                          = (q2,a) 

                                                          = q1 → ditolak

Finite State Automata (FSA)

• Model Matematika suatu sistem yang menerima input dan output diskrit
• Memiliki state yang banyaknya berhingga, dapat berpindah-pindah sari suatu state ke state yang lain
• Perubahan status = fungsi transisi

keterangan :

• lingkaran = state
• label lingkaran = nama state
• busur = transisi state
• label busur = simbol input
• lingkaran dengan busur tanpa label = state awal
• lingkaran ganda = state akhir / final