Finite State Automata

Asyer AmmayHeri Yanto Antony

Finite automata adalah model matematika sistem dengan masukan dan keluaran diskrit. Finite State Automata adalah model matematika yang dapat menerima inputan dan mengeluarkan output. Memiliki state berhingga banyaknya dan dapat berpindah dari satu ke yang lainnya sesuai dengan inputan dan fungsi transisi.

Pengertian

1. Himpunan berhingga (finite) status (state), Satu buah status sebagai status awal (initial state), biasa dinyatakan q0.Beberapa buah status sebagai status akhir (final state)

2. Himpunan berhingga simbol masukan,3. Fungsi transisi

Menentukan status berikutnya dari setiap pasang status dan sebuah simbol masukan

Setiap FSA memiliki:

Lingkaran menyatakan kedudukan state Lingkaran ganda menyatakan state akhir (final

state) Label pada lingkaran adalah nama state tersebut Busur menyatakan transisi/perpindahan state Label pada busur adalah simbol input Lingkaran didahului oleh sebuah busur tanpa label

menyatakan state awal Simbol input (0,1) State awal adalah Even State akhir adalah Odd

Even Odd

Finite automata bekerja dengan cara mesin membaca memori masukan berupa tape yaitu 1 karakter tiap saat (dari kiri ke kanan) menggunakan head baca yang di kendalikan oleh kotak kendali state berhingga, dimana pada mesin terdapat sejumlah state berhingga.

Finite automata selalu dalam kondisi yang di sebut state awal (initial state) pada saat Finite automata mulai membaca tape. Perubahan state terjadi pada mesin ketika sebuah karakter berikut di baca.

Cara kerja finite state automata

Ketika head telah sampai ,pada akhir tape dan kondisi yang di temui adalah state akhir, maka string yang terdapat pada tape dikatakan diterima Finite Automata (string-string merupakan milik bahasa bila diterima Finite automata bahasa tersebut).

Cara kerja finite state automata

Finite State Diagram (FSD)Finite State Automata dapat dimodelkan dengan Finite State Diagram (FSD) dapat juga disebut State Transition Diagram.

Finite State Diagram terdiri dari:

1. Lingkaran menyatakan stateLingkaran diberi label sesuai dengan nama state tersebut.

Adapun pembagian lingkaran adalah:- Lingkaran bergaris tunggal berarti state sementara- Lingkaran bergaris ganda berarti state akhir

2. Anak Panah menyatakan transisi yang terjadiLabel di anak panah menyatakan simbol yang membuat transisi dari 1 state ke state lain

1 anak panah diberi label start untuk menyatakan awal mula transisi dilakukan

Gambar dibawah menggambarkan perilaku FA untuk penerimaan bilangan nyata (riil) yang paling tidak mempunyai 1 digit setelah titik desimal adalah sebagai berikut:

Simpul-simpul (berbentuk lingkaran) pada FSD dibawah mengambarkan state-state dari FA, yaitu :- Simpul S- Simpul A- Simpul B

Busur dari 1 simpul ke simpul lainn menandakan transisi state. Karakter samping atau diatas busur menandakan karakter yang menyebabkan terjadinya transisi state.

Simpul dengan garis ganda menunjukkan state akhir. Digit adalah nilai 0,1,2,3,4,5,6,7,8,9

contoh

Gambar

Gambar: FSD Bilangan Nyata Dengan Minimal Satu Angka di Belakang Titik DesimalContoh string : 9.8765- Busur berlabel StartMenunjukkan transisi ke state S

- Head membaca nilai “9“Terdapat kondisi yang menunjukkan kesesuaian dengan aturan kendali pada state S yaitu adanya busur yang menunjukkan digit kembali ke state S (berarti memiliki kesesuaian bahasa)

- pembacaan ke karakter berikutnya adalah “.“Terdapat kesesuaian dengan aturan kendali pada state S, yaitu adanya busur yang menunjukkan nilai “.” ke state A (kondisi berada di state A)

penjelasan

- pembacaan karakter berikutnya = “8“Terdapat kesesuaian dengan aturan kendali yang sekarang sudah berada di state A, yaitu busur ke state B yang menunjukkan digit (kondisi berada di state B)

- pembacaan karakter berikutnya = “7“Terdapat kesesuaian dengan aturan kendali pada state B, yaitu adanya busur yang menunjukkan digit kembali ke state B (kondisi tetap berada di posisi B)

- pembacaan karakter berikutnya = “6“Terdapat kesesuaian dengan aturan kendali pada state B, yaitu adanya busur yang menunjukkan digit kembali ke state B (kondisi tetap berada di posisi B)

Penjelasan (2)

pembacaan karakter berikutnya = “5“Terdapat kesesuaian dengan aturan kendali pada state B, yaitu adanya busur yang menunjukkan digit kembali ke state B (kondisi tetap berada di posisi B)

penyesuaian aturan kendaliPada akhir pembacaan dilakukan penyesuaian apakah karakter terakhir berada pada state akhir.

Bila kesesuai kondisi “YA” maka string termasuk di dalam bahasa, dalam hal ini karakter “5″ berada pada state B yaitu state dengan lingkaran bergaris ganda yang menandakan state akhir, maka sesuai.

String 9.8765 termasuk di dalam bahasa Finite Automata pada FSD di atas.

penjelasan (3)

Contoh string : a - Busur berlabel Start

Menunjukkan transisi ke state S - Head membaca nilai “a“

Terdapat kondisi yang menunjukkan ketidaksesuaian dengan aturan kendali pada state S yaitu tidak adanya busur yang menunjukkan persamaan simbol dengan simbol yang dibaca (“a”)

- Ketidaksesuaian simbolAturan kendali pada kondisi “TIDAK” menandakan string a tidak termasuk di dalam bahasa FSD di atas.

Contoh lain

 Sistem Elevator (lift) Mesin pengeluar minuman kaleng (vending machine) Pengatur lampu lalu lintas (traffic light regulator) Sirkuit penyaklaran (switching) di komputer dan

telekomunikasi. Protokol komunikasi (communication protocol) Analisa leksikal (lexical analyzer) sistem komputer

Penerapan Finite state automata

Sekian&

Trima kasih