Deterministic Finite Automata (DFA)

Definisi formal 5-tuple, cara membaca diagram transisi, merancang DFA, dan simulasi langkah demi langkah.

Finite automaton adalah model mesin paling sederhana: mesin dengan memori terbatas (sejumlah state) yang membaca string simbol demi simbol, lalu di akhir memutuskan menerima atau menolak string itu. Himpunan semua string yang diterima disebut bahasa dari automaton tersebut.

Definisi formal

DFA adalah 5-tuple $M = (Q, \Sigma, \delta, q_0, F)$ :

Simbol	Arti
$Q$	himpunan state yang berhingga
$\Sigma$	alfabet, himpunan simbol input
$\delta : Q \times \Sigma \to Q$	fungsi transisi: dari state mana, membaca simbol apa, pindah ke state mana
$q_0 \in Q$	state awal
$F \subseteq Q$	himpunan state akhir (accepting/final)

Deterministic berarti untuk setiap pasangan (state, simbol) ada tepat satu state tujuan. Tidak ada pilihan, tidak ada transisi kosong ( $\varepsilon$ ).

String $w$ diterima jika setelah membaca seluruh $w$ dari $q_0$ , mesin berhenti di salah satu state di $F$ .

Coba simulasikan

Pada diagram, panah tanpa asal menandai state awal, dan lingkaran ganda menandai state akhir. Tekan “Baca simbol” untuk berjalan satu langkah. Tabel transisinya juga bisa diedit.

Tabel transisi δ (bisa diedit)

state	0	1	F
→q0
q1
q2

contoh:

110

Membaca simbol ke-1 dari 3…

Merancang DFA: langkah praktis

Tentukan informasi minimal yang perlu diingat setelah membaca sebagian string. Setiap kemungkinan informasi = satu state.
Tentukan state awal (informasi saat belum membaca apa pun) dan state akhir.
Untuk setiap state dan setiap simbol, tentukan state berikutnya. Jangan lupa: semua pasangan harus terdefinisi. Jika perlu, tambahkan dead state (trap) yang tidak pernah keluar.
Uji dengan beberapa string, termasuk string kosong $\varepsilon$ .

DFA dalam kode

DFA mudah sekali diimplementasikan, cukup tabel dan satu loop. Inilah inti dari lexer pada compiler dan mesin regex sederhana.

Batas kemampuan DFA

DFA hanya bisa mengenali bahasa reguler. Bahasa seperti $\{a^n b^n \mid n \ge 0\}$ (sejumlah a diikuti b yang sama banyaknya) tidak reguler. Untuk mengingat $n$ yang bisa sebesar apa pun dibutuhkan memori tak terbatas, padahal state DFA berhingga. Ini dibuktikan formal dengan pumping lemma. Bahasa seperti itu butuh mesin yang lebih kuat: pushdown automata (punya stack).