Deterministic Finite Automaton (DFA) merupakan salah satu konsep fundamental dalam teori bahasa formal dan automata. DFA sering digunakan untuk mendeskripsikan bagaimana mesin sederhana membaca rangkaian simbol dan menentukan apakah rangkaian tersebut diterima atau ditolak. Dalam dunia nyata, konsep ini digunakan pada berbagai bidang seperti kompilator, text processing, desain protokol jaringan, hingga pembuatan sistem verifikasi otomatis.
Meski terlihat abstrak, DFA sebenarnya sangat logis dan mudah dipahami jika dijelaskan langkah demi langkah. Melalui artikel ini, Anda akan memahami apa itu DFA, bagaimana cara kerja diagram transisinya, dan bagaimana menyelesaikan soal-soal yang sering muncul di perguruan tinggi maupun kompetisi informatika.
Baca juga:Kuasai Soal Kumer! Contoh Soal Dijamin Mudah Dipahami
Apa Itu DFA?
Deterministic Finite Automaton (DFA) adalah sebuah model mesin yang mempunyai jumlah keadaan terbatas dan bekerja secara deterministik. Deterministik berarti setiap keadaan dan simbol input memiliki hanya satu kemungkinan transisi. Dengan kata lain, tidak ada pilihan ganda; mesin selalu tahu kemana harus bergerak.
Sebuah DFA terdiri dari lima komponen utama:
- Q → himpunan keadaan (state)
- Σ (sigma) → himpunan simbol input atau alfabet
- δ (delta) → fungsi transisi, mengatur perpindahan state
- q₀ → keadaan awal
- F → himpunan keadaan akhir atau keadaan penerima
Jika sebuah string berakhir pada state yang termasuk dalam F, maka string tersebut diterima oleh DFA. Jika tidak, string dianggap ditolak.
Cara Kerja DFA Secara Sederhana
Untuk memahami DFA, bayangkan Anda sedang berjalan melewati beberapa ruangan. Setiap ruangan adalah state. Setiap pintu keluar di ruangan diberi label satu simbol input. Ketika Anda membaca satu simbol, Anda memilih pintu dengan label tersebut dan berpindah ke ruangan berikutnya. Karena DFA bersifat deterministik, setiap simbol hanya memiliki satu pintu.
Jika setelah membaca seluruh simbol Anda berada pada ruangan akhir (final state), maka perjalanan Anda berhasil. Jika tidak, perjalanan dinyatakan gagal.
Contoh Bentuk DFA
Misalkan kita membangun DFA untuk bahasa yang menerima string biner (0 dan 1) yang jumlah angka 1-nya genap. State yang digunakan:
- q₀ = jumlah 1 genap (juga sebagai state awal dan akhir)
- q₁ = jumlah 1 ganjil
Fungsi transisinya:
- δ(q₀, 1) = q₁
- δ(q₁, 1) = q₀
- δ(q₀, 0) = q₀
- δ(q₁, 0) = q₁
Dengan DFA ini, kita dapat mengecek apakah sebuah string memiliki jumlah 1 yang genap.
Contoh Soal dan Pembahasan DFA
Berikut kumpulan contoh soal yang sering ditemui pada perkuliahan formal languages dan automata. Setiap contoh disertai pembahasan agar konsep dapat dipahami secara mendalam.
Contoh Soal 1: Menentukan Apakah String Diterima oleh DFA
Diberikan DFA dengan aturan berikut:
- State: {q₀, q₁}
- Alfabet: {0, 1}
- q₀ adalah state awal
- q₁ adalah state akhir
- Transisi:
- δ(q₀, 0) = q₁
- δ(q₀, 1) = q₀
- δ(q₁, 0) = q₀
- δ(q₁, 1) = q₁
Apakah string 0101 diterima oleh DFA?
Penyelesaian:
Mulai dari q₀
- Baca 0 → q₁
- Baca 1 → q₁
- Baca 0 → q₀
- Baca 1 → q₀
String berakhir di q₀, bukan state akhir.
Jadi 0101 ditolak
Contoh Soal 2: DFA untuk Bahasa Bernilai Biner yang Berakhir dengan 01
Buat DFA yang menerima semua string biner yang diakhiri dengan “01”.
Analisis:
Perlu tiga state untuk mengenali pola akhir:
- q₀ → belum melihat pola
- q₁ → telah melihat 0
- q₂ → state akhir setelah membaca 01
Transisi:
- Dari q₀:
- baca 0 → q₁
- baca 1 → q₀
- Dari q₁:
- baca 0 → q₁
- baca 1 → q₂
- Dari q₂:
- baca 0 → q₁
- baca 1 → q₀
State akhir = q₂.
Contoh Soal 3: Membangun DFA untuk Bahasa yang Menerima Jumlah 0-nya Kelipatan 3
Bangun DFA yang menerima string biner dengan jumlah angka 0 merupakan kelipatan 3.
Penyelesaian:
Gunakan tiga state berdasarkan sisa pembagian jumlah 0 dengan 3:
- q₀ → jumlah 0 mod 3 = 0 (state akhir)
- q₁ → jumlah 0 mod 3 = 1
- q₂ → jumlah 0 mod 3 = 2
Transisi:
- Untuk input 0: berpindah ke state berikutnya (mod 3)
- Untuk input 1: tetap di state sekarang
DFA:
- δ(q₀, 0) = q₁
- δ(q₁, 0) = q₂
- δ(q₂, 0) = q₀
- δ(q₀, 1) = q₀
- δ(q₁, 1) = q₁
- δ(q₂, 1) = q₂
Contoh Soal 4: Menentukan Bahasa yang Diterima oleh Sebuah DFA
Diberikan DFA berikut:
- q₀ adalah state awal dan final
- Transisi:
- δ(q₀, 1) = q₁
- δ(q₀, 0) = q₀
- δ(q₁, 1) = q₀
- δ(q₁, 0) = q₁
Tentukan bahasa yang diterimanya.
Pembahasan:
DFA berpindah antara q₀ dan q₁ jika membaca angka 1.
Artinya jumlah 1 menentukan state akhir:
- q₀: jumlah 1 genap
- q₁: jumlah 1 ganjil
Karena q₀ state akhir, bahasa DFA adalah string biner dengan jumlah digit 1 genap.
Contoh Soal 5: Menerima String yang Tidak Memiliki Dua 0 Berurutan
Buat DFA yang menerima string biner yang tidak mengandung substring “00”.
Analisis:
Gunakan tiga state:
- q₀ → belum melihat 0
- q₁ → baru saja melihat 0
- q₂ → melihat 00 (state jebakan)
Transisi:
- Dari q₀:
- 0 → q₁
- 1 → q₀
- Dari q₁:
- 0 → q₂
- 1 → q₀
- Dari q₂:
- 0 → q₂
- 1 → q₂
State akhir: q₀ dan q₁.
Tips Cepat Memahami DFA
Pelajari pola bahasa
Cobalah menganalisis jenis bahasa dari soal sebelum membangun DFA.
Gunakan pendekatan sisa modulo
Sangat berguna untuk bahasa yang menghitung jumlah karakter.
Buat diagram transisi
Visualisasi membantu menghindari kesalahan logika.
Pahami cara kerja state jebakan
State ini digunakan untuk menangani pola yang harus ditolak.
Latihan dengan berbagai variasi
Semakin banyak latihan, semakin cepat Anda memahami pola automata.
Penutup
DFA merupakan fondasi penting dalam teori komputasi dan banyak diterapkan pada berbagai teknologi modern. Dengan memahami struktur, cara kerja, serta teknik membangun dan membaca DFA, Anda memperoleh dasar yang kuat untuk mempelajari bidang komputasi yang lebih dalam seperti NFA, regex, kompilasi, dan automata kompleks lainnya. Contoh-contoh soal di atas diharapkan dapat membantu Anda memahami konsep DFA secara praktis. Jika Anda ingin dibuatkan kumpulan soal tambahan, diagram automata, atau versi pembahasan yang lebih mendalam, saya siap membantu kapan saja.
Penulis: Maharani Noeralifa
Post Comment