Desain Penyusun - Automata Hingga
Automata hingga adalah mesin negara yang mengambil serangkaian simbol sebagai input dan mengubah statusnya sesuai dengan itu. Automata terbatas adalah pengenal ekspresi reguler. Ketika string ekspresi reguler dimasukkan ke automata hingga, statusnya untuk setiap literal berubah. Jika string input berhasil diproses dan automata mencapai status akhirnya, itu diterima, yaitu string yang baru saja diumpankan dikatakan sebagai token valid dari bahasa yang ada.
Model matematis dari finite automata terdiri dari:
- Himpunan negara hingga (Q)
- Kumpulan simbol input hingga (Σ)
- Status Satu Mulai (q0)
- Kumpulan keadaan akhir (qf)
- Fungsi transisi (δ)
Fungsi transisi (δ) memetakan himpunan keadaan hingga (Q) ke himpunan simbol masukan hingga (Σ), Q × Σ ➔ Q
Konstruksi Automata Hingga
Misalkan L (r) menjadi bahasa biasa yang dikenali oleh beberapa automata terbatas (FA).
States: Serikat FA diwakili oleh lingkaran. Nama negara bagian ditulis di dalam lingkaran.
Start state: Keadaan tempat automata dimulai, dikenal sebagai status mulai. Status awal memiliki panah yang mengarah ke sana.
Intermediate states: Semua negara bagian perantara memiliki setidaknya dua anak panah; satu menunjuk ke dan satu lagi menunjuk dari mereka.
Final state: Jika string input berhasil diurai, automata diharapkan berada dalam status ini. Keadaan akhir diwakili oleh lingkaran ganda. Mungkin ada jumlah panah ganjil yang menunjuk ke sana dan jumlah panah genap yang menunjuk ke luar darinya. Jumlah panah ganjil satu lebih besar dari genap, yaituodd = even+1.
Transition: Transisi dari satu keadaan ke keadaan lain terjadi ketika simbol yang diinginkan dalam masukan ditemukan. Setelah transisi, automata dapat berpindah ke status berikutnya atau tetap dalam status yang sama. Perpindahan dari satu keadaan ke keadaan lain ditampilkan sebagai panah terarah, dimana panah menunjuk ke keadaan tujuan. Jika automata tetap di status yang sama, panah yang menunjuk dari status ke dirinya sendiri akan ditarik.
Example: Kami berasumsi FA menerima tiga digit nilai biner yang diakhiri dengan digit 1. FA = {Q (q 0 , q f ), Σ (0,1), q 0 , q f , δ}
