Finite State Automata
Finite State Automata (FSA) adalah mesin paling sederhana dalam Teori Bahasa dan Otomata. Bayangkan sebuah mesin dengan beberapa "ruangan" yang disebut state. Mesin itu cuma bisa ingat sedang di ruangan mana saat ini, tidak bisa mengingat apa pun sebelumnya. Setiap kali membaca satu karakter, mesin berpindah ke ruangan lain sesuai aturan yang sudah ditentukan. Di halaman ini, FSA dipakai buat membangun tokenizer (pemecah ekspresi jadi potongan-potongan kecil bermakna, disebut token), persis seperti langkah pertama yang dilakukan compiler sungguhan sebelum kode program dieksekusi.
Satu DFA tunggal membaca ekspresi karakter demi karakter. Setiap state akhir ditandai kategori
token (NUMBER, PLUS, MINUS, STAR, SLASH, LPAREN, RPAREN). Strategi maximal munch dipakai
persis seperti lexer pada compiler sungguhan: ambil kecocokan terpanjang sebelum berhenti, jadi
12 dibaca sebagai satu token NUMBER, bukan dua token angka "1" dan "2" terpisah.
Nama state seperti NUMDOT/LPAREN dijelaskan di halaman Panduan.
Definisikan mesin dengan format teks di bawah, lalu uji sebuah string apakah diterima atau ditolak. Tipe mesin (DFA atau NFA) terdeteksi otomatis dari definisinya: kalau ada satu state yang punya dua tujuan berbeda untuk simbol yang sama, atau ada transisi-ε, berarti itu NFA.
states, alphabet, start,
final diisi daftar dipisah koma. Baris selanjutnya berformat
state_asal simbol state_tujuan, satu transisi per baris. Simbol eps berarti
transisi-ε (tanpa membaca karakter apa pun).
NFA boleh "bingung" (dari satu state, satu simbol bisa menuju lebih dari satu state tujuan, bahkan boleh pindah state tanpa membaca apa pun lewat transisi-ε). Komputer tidak suka mesin yang bingung, jadi NFA perlu diubah dulu jadi DFA yang pasti sebelum benar-benar dieksekusi secara efisien. Setiap state DFA hasil konversi sebenarnya adalah himpunan beberapa state NFA sekaligus.