Matematika Diskrit

FINITE AUTOMATA

Untuk mengerti tentang finite automata, berikut ini diberikan satu contoh finite autumata untuk menggambarkan parity checking (Recognizer).

- FA digambarkan dalam bentuk graph berarah (direct graph)

- Dalam FA diatas, checking dimulai dari state even (genap); proses berakhir (dengan kebenaran) jika berakhir pada state odd (ganjil)

- Periksa kebenaran string-string be-rikut :

010100110 ® (salah / rejected)

100011110 ® (benar / accepted)

001111001 ® (benar / accepted

Catatan :

· ilustrasi diatas merupakan contoh sederhana dari FA

· FA sering digunakan sebagai model komputasi untuk menentukan apakah suatu string dianggap valid (acceptable) untuk tujuan tertentu

· Walaupun FA bukan merupakan model komputasi terbaik, namun merupakan medium pemahaman yang penting sebelum melangkah ke model-model yang lebih kompleks (PDA dan TM)