FINITE AUTOMATA - IMPLEMENTASI SCENNER

 FINITE AUTOMATA

Finite Automata

Finite automata adalah mesin abstrak berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata di mana sistem dapat berada di salah satu dari sejumlah berhingga konfigurasi internal disebut state. Beberapa contoh sistem dengan state berhingga antara lain pada mesin minuman otomatis atau vending machine, pengatur lampu lalu lintas dan lexical analyser. 

Suatu finite automata terdiri dari beberapa bagian. Finite automata mempunyai sekumpulan state dan aturan-aturan untuk berpindah dari state yang satu ke state yang lain, tergantung dari simbol nya. Finite automata mempunyai state awal, sekumpulan state dan state akhir. Finite automata merupakan kumpulan dari lima elemen atau dalam bahasa matematis dapat disebut sebagai 5-tuple. 

DEFINISI

Otomata Hingga (AH)/Automata Hingga (AH)/Finite Automata (FA) didefinisikan sebagai pasangan 5 tupel: (K, VT , M, S, Z).

𝐾 : himpunan hingga stata,
𝑉𝑇 : himpunan hingga simbol input (alfabet)
𝑀 : fungsi transisi, menggambarkan transisi stata AH akibat pembacaan simbol input. Fungsi transisi ini biasanya diberikan dalam bentuk tabel.
𝑆 ∈ 𝐾 : stata awal
𝑍 ⊂ 𝐾 : himpunan stata penerima

Ada 2 jenis Finite Automata

1. Deterministic FA (DFA), dimana transisi stata FS merupakan akibat dari pembacaan sebuah simbol bersifat tertentu;
2. Non-Deterministic FA (NFA), dimana transisi stata FS merupakan akibat dari pembacaan sebuah simbol bersifat tak tentu

IMPLEMENTASI SCENNER

Scanner biasanya diimplementasikan sebagai sebuah prosedur yang dipanggil oleh Parser.Prosedur Scan sederhana:Didefinisikan dulu Procedure GetChar untuk mengambil sebuah karakter dari file input.Procedure GetChar;beginRead (FileInput, Kar);end;
Klasifikasi Token

• Identifier => Kumpulan huruf dan angka, diawali huruf contoh : a1, panjang2, lingkaran, dll
• Integer => Kumpulan angka contoh : 0, 23, 000, 001
• Keyword => Kata-kata kunci dalam suatu bahasa contoh : if, else, procedure
• Whitespace => tab, baris baru (newlines), spasi (blanks)