Finite State Automata

 Finite State Automata

A. Pengertian

    FSA (Finite State Automata) adalah alat atau tool yang berguna dalam merancang lexical analyzer,        yaitu bagian dari kompilator yang mengelompokan karakter-karakter ke dalam sebuah token, yang         berupa unit terkecil seperti nama, variabel, dan keyword. FSA dipakai untuk penganalisa leksikal dan     dipakai juga dalam text editor, pemrosesan teks, dan program file-searching

B. Contoh Implementasi

    

    Keterangan :
    1. Mesin ini memiliki 6 state : (q0,q1,q2,q3,q4,q5). 
    2. State awal q0
    3. Sedangkan q3 dan q4 adalah state akhir, dan 
    4. Simbol input adalah (a,d,u)

C. Jenis FSA

    1. DFA (Deterministic)
        Pada setiap input, hanya ada satu keadaan (state) tujuan dari keadaan saat ini. Terdiri dari 5 tuple.
        Diagram Transisi / State Diagram :
        1. Tiap keadaan merupakan simpul 
        2. Tiap keadaan q anggota Q dan tiap simbol a anggota himpunan, dituliskan sebagai &(q,a) = p.                Artinya, diagram transisi memiliki panah dari q ke p, yang berlabel a. 
        3. Keadaan awal (q0 ) ditandai dengan adanya panah tanpa sumber. 
        4. Simpul yang menjadi keadaan final ditandai dengan lingkaran bergaris tepi ganda 

    2. Tabel Transisi
        1. Representasi daftar dari suatu fungsi 
        2. Baris menunjukkan keadaan dan kolom menunjukkan input. 
        3. Isi dari baris menunjukkan keadaan q dan isi dari kolom input a menunjukkan keadaan                       &(q,a)

    2. NFA (Non deterministic)
        Pada setiap input terdapat lebih dari satu keadaan tujuan dari keadaan saat ini.

D. Contoh soal DFA 
     Soal : M = (Q, E, &, s, F), dimana : Q = {q0 , q1 }, E = {a,b}, S = q0 , F = {q0 }
     Jawaban :    
     1. Tabel Transisi 
          

    2. Diagram State 
        

    
    

    Jika M diberi input aabba, dengan state awal (q0 , aabba), maka :
    (q0 ,aabba)
         ├M (q0 ,abba)
         ├M (q0 ,bba)
         ├M (q1 ,ba)
         ├M (q0 ,a)
         ├M (q0 ,e)
Karena (q0 ,aabba)
├* M (q0 ,e), jadi aabba diterima oleh M