Teori Bahasa Dan Automata - Finite State Automata

Dibuat Oleh pada
Assalamualaikum Wr. Wb.

Pada postingan ini saya akan membagikan sebuah materi Finite State Automata. Tujuan saya membuat postingan ini adalah untuk memenuhi Tugas Materi 7 pada Mata Perkuliahan TEORI BAHASA DAN AUTOMATA.

Pada postingan kali ini saya akan membahas 5 topik utama yaitu:
1. Penerapan FSA (Finite State Automata)
2. Penerapan DFA (Deterministic Finite Automata)
3. Penerapan NFA (Nondeterministic Finite Automata)
4. Ekuivalen antar DFA
5. Reduksi Jumlah State

 Berikut adalah pembahsannya

1. Penerapan FSA (Finite State Automata)

Finite State Automata/otomata berhingga state, selanjutnya disebut sebagai FSA yaitu suatu model matematika dari suatu sistem yang menerima input dan output diskrit. FSA merupakan mesin otomata dari bahas regular. Suatu FSA memiliki state yang banyaknya berhingga dan dapat berpindah-pindah dari suatu state ke state lain. Perubahan state ini dinyatakan oleh fungsi transisi. FSA tidak memiliki tempat penyimpanan, sehingga kemampuan ‘mengingatnya’ terbatas, hanya bisa mengingat state yang terkini. Contoh FSA antara lain elevator, text editor, analisa leksikal, protocol komunikasi jaringan dan pencek parity. FSA berdasar pada pendefinisian kemampuan berubah state-statenya bisa dibagi menjadi Deterministic Finite Automata (DFA) dan Non-deterministic Finite Automata (NFA).

Secara formal FSA dinyatakan oleh 5 tupel atau M = (Q, Σ, δ, S, F) dimana:
Q = himpunan state/kedudukan
Σ = himpunan simbol input/masukan/abjad
δ = fungsi transisi
S = state awal/kedudukan awal (initial state), S є Q
F = himpunan state akhir, F ∩ Q (jumlah state akhir pada suatu FSA bisa lebih dari satu)

 FSA juga terbagi menjadi dua jenis, yaitu:
  • DFA (Deterministic Finite Automata)
Artinya: Dari suatu state ada tepat satu state berikutnya untuk setiap simbol input yang diterima
  • NFA/NDFA (Nondeterministic Finite Automata)
Artinya: Dari suatu state bisa terdapat 0, 1 atau lebih busur keluar (transisi) berlabel simbol input yang sama

2. Penerapan DFA (Deterministic Finite Automata)

Deterministic Finite Automata/otomata berhingga deterministik, selanjutnya disebut sebagai DFA. Pada DFA, dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima. Suatu string x dinyatakan diterima bila δ(S, x) berada pada state akhir/final state.

Contoh:
Tabel DFA
Gambar Finite DFA


3. Penerapan NFA (Nondeterministic Finite Automata)

Non-deterministic Finite Automata, selanjutnya disebut sebagai NFA. Pada NFA, dari suatu state bisa terdapat 0 atau 1 atau lebih busur keluar (transisi) berlabel symbol input yang sama. Suatu string diterima oleh NFA bila terdapat suatu urutan transisi sehubungan dengan input string tersebut dari state awal menuju state akhir. Untuk NFA, maka harus mencoba semua kemungkinan yang ada sampai terdapat satu yang mencapai state akhir.
  • NFA mempunyai fungsi transisi yang menetapkan nol atau lebih state untuk sebuah symbol input
  • NFA menerima String, jika hasil akhir penelusuran string berakhir di salah satu final state
  • String akan diterima apabila ada suatu path bervariabel w dari start state ke salah satu final state, maka w akan diterima
Contoh:
Tabel NFA
Gambar Finite NFA


Berdasarkan contoh Deterministic Finite Automata (DFA) dan Non Deterministic Finite Automata (NFA) yang ada di atas, terlihat perbedaan antara DFA dan NFA yaitu:
  • Pada Deterministic Finite Automata, jika suatu state diberi inputan maka state tersebut akan selalu tepat menuju satu state
  • Pada Non Deterministic Finite Automata, jika suatu state diberi inputan maka mungkin saja bisa menuju ke beberapa state berikutnya. Dapat dilihat di S0, jika diberi inputan b bisa menuju ke S1 dan S2

4. Ekuivalen antar DFA

Gambar Hubungan antara DFA, NFA, dan Ekspresi Reguler

 Hubungan antara DFA, NFA, dan Ekspresi Reguler
Dua DFA M1 dan M2 dinyatakan ekivalen apabila L (M1) = L (M2)
Gambar DFA M1 dan DFA M2


5. Reduksi Jumlah State

Untuk suatu bahasa regular, kemungkinan ada sejumlah Deterministic Finite Automata yang dapat menerimanya. Perbedaannya hanyalah jumlah state yang dimiliki otomata-otomata yang saling ekuivalen tersebut. Tentu saja, dengan alasan kepraktisan, kita memilih otomata dengan jumlah state yang lebih sedikit.

Sasaran kita di sini adalah mengurangi jumlah state dari suatu Finite State Automata, dengan tidak mengurangi kemampuannya semula untuk menerima suatu bahasa.

 Ada dua buah istilah baru yang perlu kita ketahui yaitu:
  • Distinguishable yang berarti dapat dibedakan
  • Indistinguishable yang berarti tidak dapat dibedakan
Reduksi Jumlah State pada FSA:
  • Reduksi dilakukan untuk mengurangi jumlah state tanpa mengurangi kemampuan untuk menerima suatu bahasa seperti semula.
  • State pada FSA dapat direduksi apabila terdapat useless state.
  • Hasil FSA yang direduksi merupakan ekivalensi dari FSA semula.
Keterangan:
Useless state adalah state yang tidak menerima inputan dari manapun tetapi mengeluarkan output.

Gambar Finite FSA

Pembahasan:
(q0, q1)
q0,0 --> q1 & q1,0 --> q1 --> q1,q1 --> indistinguisable, sehingga dapat direduksi.

Contoh Soal:
Gambar Finite Contoh Soal Reduksi State FSA

 Penyelesaian:
Didapat State yang tidak useless: q0, q1, q2, q3, q4
  • q0, q1 -> distinguishable
  • q0, q2 -> distinguishable
  • q0, q3 -> distinguishable
  • q0, q4 -> distinguishable
  • q1, q2 -> indistinguishable
  • q1, q3 -> indistinguishable
  • q1, q4 -> distinguishable
  • q2, q3 -> indistinguishable
  • q2, q4 -> distinguishable
  • q3, q4 -> distinguishable
Pembuktian:
(q0, q1)
q0, 0 -> q1 & q1, 0 -> q2 =>q1, q2
q0, 1 -> q3 & q1, 1 -> q4 => q3, q4 = distinguisable

(q0, q2)
q0, 0 -> q1 & q2, 0 -> q1 =>q1, q1
q0, 1 -> q3 & q2, 1 -> q4 => q3, q4 = distinguisable

(q0, q3)
q0, 0 -> q1 & q3, 0 -> q1 =>q1, q1
q0, 1 -> q3 & q3, 1 -> q4 => q3, q4 = distinguisable

(q1, q3)
q1, 0 -> q2 & q3, 0 -> q2 =>q2, q2
q1, 1 -> q4 & q3, 1 -> q4 => q4, q4 = indistinguisable

(q1, q2)
q1, 0 -> q2 & q2, 0 -> q1 =>q1, q2
q1, 1 -> q4 & q2, 1 -> q4 => q4, q4 = indistinguisable

(q2, q3)
q2, 0 -> q1 & q3, 0 -> q2 =>q1, q2
q2, 1 -> q4 & q3, 1 -> q4 => q4, q4 = indistinguishable
Maka dapat direduksi menjadi:
Gambar Contoh Soal Hasil Reduksi FSA

 Sekian materi yang saya posting di blog ini. Mohon maaf apabila ada kekurangan dan kesalahan dalam penulisan. Semoga dapat bermanfaat bagi kita semua

Terima Kasih

Wassalamualaikum Wr. Wb.

 Penulis
Nama: Dharma Ajie Nur Rois
NPM: 1810 6311 70120
Kelas: 4G Fasilkom
-----------------------------------------------------------------------------------------------------------------------------------------------
DAFTAR PUSTAKA

Komentar

Posting Komentar