Finite Automata 2

Kalau sebelumnya kita medefinisikan sebuah mesin menjadi menjadi konfigurasi transisinya, kita bisa juga melakukan sebaliknya yaitu dengan menggunakan tabel dan fungsi transisi, menjadi mesin Deterministic Finite Automata (DFA).

Maka mesin DFA nya adalah:

Non Deterministic Finite Automata (NFA)

Pada Non Deterministik Finite Automata (NFA), dari satu state bisa terdapat 0, 1 atau lebih busur keluar (transisi) berlabel simbol input yang sama. NFA didefinisikan pula dengan 5 tuple dengan arti yang serupa dengan Deterministic Finite Automata (DFA). Disini perbedaan ada pada fungsi transisinya, dimana untuk setiap pasangan state input bisa memiliki 0 (nol) atau lebih pilihan untuk state berikutnya.

Dari stae q0 terdapat dua busur keluar yang berlabelkan a. Dari stae q0 bilan mendapatkan input a, bisa berpindah ke state q0 atau q1 yang secara formal dinyatakan: δ(q0,a) = {q0,q1}. Maka Automata ini kita sebut Non Deterministic Automata (Tidak pasti arahnya).

Perhatikan cara penulisan state hasil pada tabel transisi untuk NFA digunakan kurung kurawal ‘{‘ dan ‘}’ , karena hasil transisinya merupakan suatu himpunan state.

Ekivalensi antar Deterministic Finite Automata

Misalkan terdapat dua buah DFA, M1 dan M2, yang masing-masing menerima L(M₁) dan L(M₂). Jika L(M₁) = L(M₂) maka 2 DFA tersebut ekivalen.

Contoh lain yang ekivalen (M3, M4)

Untuk suatu bahasa reguler, kemungkinan ada sejumlah DFA yang menerimanya. Perbedaannya hanya jumlah state yang dimiliki oleh otomata-otomata yang saling ekivalen.

Reduksi Jumlah State pada Finite State Automata

Salah satu cara untuk meresuksi suatu DFA bisa dilakukan dengan mengkombinasikan state yang distinguishable. Tahapan-tahapannya sebagai berikut:

1. Hapuskan semua state yang tidak dapat dicapai dari state awal dari jalan manapun
2. Buatkan semua pasangan state (p,q), yang distinguishable, dimana p ∈ F, q ∉ F.
3. Untuk semua state lakukan pencarian state yang distinguishable dengan aturan untuk semua (p,q) dan semua a ∈ ∑, hitunglah δ (p,a) = p_a, dan δ (q,a) = q_a. Jika pasangan (p_a,q_a) telah tercatat sebagai distinguishable maka pasangan (p,q) juga dimasukan sebagai distinguisable.
4. Dari hasil nomor 3 kita mendapatkan pasangan state yang distinguishable. Pasangan-pasangan lain yang tidak termasuk ke dalam state distinguishable tersebut (sisanya) dapat ditentukan sebagai state yang indistinguishable.
5. Beberapa state yang saling indistinguishable dapat digabungkan ke dalam state.
6. Sesuaikan transisi dari dan ke state gabungan tersebut.

Berikut mesin DFA yang dapat kita reduksi:

Hasil DFA yang telah direduksi statenya . Kedua mesin tersebut akan tetap menerima bahasa yang sama.