NON-DETERMINISTIC FINITE AUTOMATA (NFA)

Mesin model Non-Deterministic Finite Automata (NFA) sangat mirip dengan DFA, hanya berbeda pada fungsi transisinya yaitu dapat memiliki 0, atau lebih fungsi transisi. Pada gambar diagram transisi/state terlihat untuk input yang sama busur panah keluar dari suatu state bisa saja tidak ada, bisa hanya satu, bisa ada dua atau lebih.

Contoh: {Q = ({q₀, q₁, q₂, q₃, q₄}, Σ = {0,1}, S= q₀, F = { q₂ , q₄}}, dengan tabel fungsi transisi sebagai berikut.

d	0	1
q₀	{ q₀,q₃}	{q₀,q₁}
q₁	{e}	{q₂}
q₂	{q₂}	{q₂}
q₃	{q₄}	{e}
q₄	{q₄}	{q₄}

Non-Deterministic Finite Automata

Perhatikan bahwa dalam table transisi, state-state dituliskan dalam kurung kurawal, yang berarti bahwa hasil transisinya/state yang dituju adalah himpunan state-state.

Pada gambar 3.1 terlihat bahwa dari state q₀ terdapat dua busur keluar yang berlabel input “0”, yaitu kembali ke q₀ dan satu busur lagi menuju ke state q₃. Demikian pula apabila mendapat input “1”, terdapat dua busur keluar yang berlabel input “1”, yaitu kembali ke q₀ dan satu busur lagi menuju ke state q₁. Pada state q₁ hanya ada satu busur keluar yaitu yang berlabel input “1”, menuju ke state q₂, sedangkan yang berlabel input “0” tidak ada. Pada state q₃ tidak terdapat input berlabel “1”, hanya input berlabel “0” yang menuju ke sate q₄. Secara formula dapat dituliskan:

1. d(q₀ ,0) = {q₀, q₃}, baca: transisi state q₀ mendapat input “0”, menuju ke state q₀, dan state q₃.

2. d(q₀ ,1) = {q₀, q₁}, baca: transisi state q₀ mendapat input “1”, menuju ke state q₀, dan state q₁.

3. d(q₁ ,1) = {q₂}, baca: transisi state q₁ mendapat input “1”, menuju ke state q₂.

4. d(q₃ ,0) = {q₄}, baca: transisi state q₃ mendapat input “0”, menuju ke state q_4.

5. d(q₂ ,0) = d(q₂, 1) ={q₂}, baca: transisi state q₂ mendapat input “0”, maupun mendapat input “1” menuju ke state q₂.

6. d(q₄ ,0) = d(q₄ ,1) ={q₄}, baca: transisi state q₄ mendapat input “0”, maupun mendapat input “1” menuju ke state q₄.

Suatu string diterima NFA bila terdapat suatu urutan transisi berdasar input, dari state awal ke state akhir. Suatu transisi berdasarkan input yang tidak berakhir pada state akhir dapat dikatakan bahwa input yang dimaksud tidak diterima oleh mesin NFA tersebut. Untuk mengetahui apakah suatu string diterima atau tidak harus dilakukan percobaan untuk semua kemungkinan.

Contoh : string 01001

Contoh String

Ekivalensi Antar Deterministic Finite Automata

Misalkan terdapat dua buah FSA, M1 dan M2, yang masing-masing menerima bahasa L(M1) untuk mesin M1 dan L(M2) untuk mesin M2, maka disebut ekuivalen apabila kedua FSA tersebut menerima bahasa yang sama yaitu L(M1) = L(M2)

Contoh : FSA yang menerima bahasa {aⁿ | n³0 }

Gambar FSA

Reduksi Jumlah State pada FSA

Untuk suatu bahasa regular, kemungkinan ada banyak mesin FSA yang dapat menerima bahasa tersebut, perbedaannya hanyalah pada jumlah state yang dimiliki oleh FSA-FSA yang saling ekivalen tersebut. Suatu FSA akan lebih praktis apabila memiliki jumlah state yang lebih sedikit.

Dua buah state dari FSA disebut indistinguishable (tidak dapat dibedakan) apabila :

d(q,w)ÎF sedangkan d(p,w) Î F dan

d(q,w) ÏF sedangkan d(p,w) ÏF untuk semua w Î S^*

Dua buah state dari FSA disebut distinguishable (dapat dibedakan) bila terdapat w Î S^*sedemikian hingga:

d(q,w)ÎF sedangkan d(p,w)ÏF dan

Salah satu cara untuk mereduksi/mengurangi jumlah state dari suatu mesin FSA adalah dengan mencari kombinasi state yang distinguishable. Prosedur menentukan pasangan status indistinguishable:

1. Hapus semua state yang tak dapat dicapai dari state awal.

2. Catat semua pasangan state (p,q) yang distinguishable, yaitu {(p,q) | p Î F Ù q Ï F}

3. Untuk semua state lakukan pencarian state yang distinguishable dengan aturan apabila d(p,a) = p_a dan d(q,a) = q_a,jika pasangan (p_a,q_a) sudah tercatat sebagai pasangan yang distinguishable, maka pasangan (p,q) tersebut juga dimasukkan sebagai distinguishable.

4. Untuk setiap pasangan (p,q) yang tidak termasuk dalam distinguishable, maka pasangan tersebut adalah pasangan state yang indistinguishable.

5. Beberapa state yang saling indistinguishable dapat digabungkan ke dalam satu state.

6. Sesuaikan transisi dari dan ke state-state gabungan tersebut

Contoh: Lakukan pengurangan/reduksi state dari gambar 3.4 di bawah ini

Mesin DFA 5 state

1. Hapus state yang tidak tercapai dari state awal à semua dapat dicapai

2. Pasangan distinguishable (q₀,q₄), (q₁,q₄), (q₂,q₄), (q₃,q₄).

3. Pasangan sisanya (q₀,q₁), (q₀,q₂), (q₀,q₃), (q₁,q₂) (q₁,q₃) (q₂,q₃)

pasangan	state 1		state 2		Hasil
pasangan	0	1	0	1	Hasil
(q₀,q₁)	q1	q3	q2	q4	distinguishable
(q₀,q₂)	q1	q3	q1	q4	distinguishable
(q₁,q₂)	q2	q4	q3	q4	indistinguishable
(q₀,q₃)	q1	q3	q2	q4	distinguishable
(q₁,q₃)	q2	q4	q2	q4	indistinguishable
(q₂,q₃)	q1	q4	q2	q4	indistinguishable

Perhatikan pasangan state ketika mendapat input 1, untuk pasangan (q₁,q₂), (q₁,q₃), (q₂,q₃) menghasilkan state hanya q₄, sehingga pasangan-pasangan ini disebut indistinguishable, dan dalam penggambaran dapat disatukan.

Catatan : jumlah pasangan seluruhnya :

Prosedur Reduksi DFA

Tentukan pasangan status indistinguishable.

Gabungkan setiap group indistinguishable state ke dalam satu state dengan relasi pembentukan group secara berantai : Jika p dan q indistingishable dan jika q dan r indistinguishable maka p dan r indistinguishable, dan p,q serta r indistinguishable semua berada dalam satu group.

sesuaikan transisi dari dan ke state-state gabungan.

Contoh

pasangan status indistinguishable (q₁,q₂), (q₁,q₃) dan (q₂,q₃).

q₁,q₂,q₃ ketiganya dapat digabung dalam satu state q₁₂₃

Menyesuaikan transisi, sehingga DFA menjadi