Ekuivalensi Antar Deterministic Finite Automata (DFA)

Ekuivalensi Antar Deterministic Finite Automata (DFA) 

Tujuan:
Mengurangi jumlah state dari suatu Finite State Automata,dengan tidak mengurangi kemampuannya semula untuk menerima suatu bahasa.

Pasangan state dapat dikelompokkan berdasarkan:

1. Distinguishable State (Dapat Dibedakan)



2. Indistinguishable State (Tidak Dapat Dibedakan)




Reduksi Jumlah State Pada FSA

Reduksi dilakukan untuk mengurangi jumlah state tanpa mengurangi kemampuan untuk menerima suatu bahasa seperti semula(efisiensi). State pada FSA dapat direduksi apabila terdapat useless state. Hasil dari FSA yang direduksi merupakan ekivalensi dari FSA semula.


Biasanya DFA diwakili oleh 5-tuple (Q, ∑, δ,Q0, F) dimana:

  • Q adalah himpunan terbatas state.
  • ∑ adalah himpunan terbatas simbol yang disebut alfabet.
  • δ adalah fungsi transisi di mana δ: Q × ∑ → Q
  • q0 adalah keadaan awal dari mana input diproses (Q0∈ Q).
  • F adalah himpunan keadaan akhir/keadaan akhir dari Q (F ⊆ Q).

Contoh Sebuah Mesin DFA



Lakukan reduksi pada state DFA diatas?


Penyelesaian:

1. State q5 merupakan useless state

2. Pasangan State:

    - (q0,q1)
    - (q0,q2)
    - (q0,q3)
    - (q0,q4)
    - (q1,q2)
    - (q1,q3)
    - (q1,q4)
    - (q2,q3)
    - (q2,q4)
    - (q3,q4)

3. Reduksi Jumlah State Pada FSA - Step

    - (q0,q1)
    - (q0,q2)
    - (q0,q3) -> Distinguishable
    - (q0,q4) -> Distinguishable
    - (q1,q2)
    - (q1,q3) -> Distinguishable
    - (q1,q4) -> Distinguishable
    - (q2,q3) -> Distinguishable
    - (q2,q4) -> Distinguishable
    - (q3,q4) -> Distinguishable

    - Pasangan (q0,q1): Distinguishable
       => (q0,0) = q1 dan (q1,0) = q2
            : (q1,q2)

       => (q0,1) = q2 dan (q1,1) = q3
            : (q2,q3) -> Distinguishable

     - Pasangan (q0,q2): Distinguishable
       => (q0,0) = q1 dan (q2,0) = q2
            : (q1,q2)

       => (q0,1) = q2 dan (q2,1) = q4
            : (q2,q4) -> Distinguishable

     - Pasangan (q1,q2): Distinguishable
       => (q1,0) = q2 dan (q2,0) = q2
            : (q2,q2)

       => (q1,1) = q3 dan (q2,1) = q4
            : (q3,q4) -> Distinguishable

4. Pasangan State

    - (q0,q1) -> Distinguishable
    - (q0,q2) -> Distinguishable
    - (q0,q3) -> Distinguishable
    - (q0,q4) -> Distinguishable
    - (q1,q2) -> Distinguishable
    - (q1,q3) -> Distinguishable
    - (q1,q4) -> Distinguishable
    - (q2,q3) -> Distinguishable
    - (q2,q4) -> Distinguishable
    - (q3,q4) -> Distinguishable

5. Hasil DFA Yang Direduksi









Comments

Post a Comment

Popular posts from this blog

Merubah NFA Dengan E - Move Ke NFA Tanpa E - Move

Image
Dari  sebuah Non-deterministic  Finite  Automata  dengan E -move  dapat  kita peroleh Non-  deterministic  Finite  Automata  tanpa E -move  yang  ekivalen. Berikut ini diberikan beberapa contoh NFA dengan E - Move dan tanpa E - Move. Gambar 1. NFA dengan E - Move Pada gambar diatas terlihat bahwa q0 membawa sebuah input empty ke q1. Sedangkan berikut dibawah ini gambar NFA tanpa E - Move Gambar 2. NFA tanpa E - Move Berikut tahapan  untuk  mendapatkan perubahan dari Non-deterministic Finite Automata E - move  ke Non - deterministic Finite Automata tanpa E -move. Caranya  secara  umum adalah sebagai berikut: Buat table transisi Non-deterministic Finite Automata dengan E - move semula Tentukan E - closure untuk setiap state Carilah   setiap   fungsi   transisi   hasil   perubahan   dari   Non-deterministic Finite Automata E - move ...
Read more