Materi 3

FINITE STATE AUTOMATA(FSA)

FSA (FInite State Automata) merupakan tool yang sangat berguna dalam perancangan lexical analyzer, yaitu bagian dari kompilator yang mengelompokkan karakter-karakter ke dalm sebuah token, yang berupa unit terkecil seperti nama, variabel, dan kerword, 
FSA dipai untuk penganalisa leksikal dan dipakai juga dalm text editor, pemrosesan teks, dan program file-searching.

FSA atau AH (Automata Hingga) didefinisikan sebagai pasangan 5 tupel → M = (Q, Σ, δ, S, F).
Keterangan :
    Q : himpunan hingga state
    Σ : himpunan hingga simbol input (alfabet)
    δ :fungsi transisi, menggambarkan transisi state FSA akibat pembacaan simbol input.

Fungsi transisi ini biasanya diberikan dalam bentuk tabel.
S ∈ Q : state AWAL
F ⊆ Q : himpunan state AKHIR

• Mesin ini memiliki 6 state, (q0, q1, q2, q3, q4, q5),
• state awal q0,
• sedangkan q3 dan q4 adalha state akhir, dan
• simbol input adalah (a, d, u)

CONTOH FINITE STATE AUTOMATA

• Tabel transisi

• Diagram Transisi

• contoh : FSA untuk mengecek parity ganjil
• Q = {Ganjil, Genap}
• ∑ = {0,1}
• S = Genap
• F = Ganjil

DEFINISI FORMAL FSA 

M = (Q, Σ, δ, S, F) dimana : 
Q = abjad, himpunan simbol input/masukan
δ = fungsu transisi, δ : Q x Σ → Q
S = state awal / initial state
F = himpunan state akhir / final state

    

FSA Trbagi menjadi 2 :

1. Deterministic (DFSA/DFA)

• pada setiap input, hanya ada satu keadaan (state) tujuan dari keadaan saat ini.
• DFA terdiri atas 5 tuple, yaitu A = (Q, Σ, δ, q0, F)
• Notasi Lain DFA :

1. Diagram Transisi / State Diagram

• Tiap keadaan merupakan simpul
• Tiap keadaan q ∈ Q dan setiap simbol a ∈ ∑, dituliskan sebagai δ(q,a) = p. Artinya, diagram transisi memiliki panah dari q ke p, yang berlabel a.
• keadaan awal (q៰) ditandai dengan adanya panah tampa sumber.
• simpul yang menjadi keadaan final di tandai dengan lingkaran bergaris tepi ganda.

             2.  Tabel Transisi

• Representasi daftar dari suatu fungsi
• Baris menunjukkan keadaan dan kolom menunjukkan input.
• isi dari bari smenunjukkan keadaan q dan isi dari kolom input a menunjukkan keadaan δ(q,a).
• Contoh DFA
• Contoh DFA yang dapat menerima string berakhir 01
• A = ({q0, q1, q2}, {0,1}, δ, q0, {q2}) dengan fungsi transisi δ diberikan dalam bentuk tabel :
• State Diagram 
• 

2. Non Deterministic (NFSA/NFA)

• Pada setiap input terdapat lebih dari satu keadaan tujuan dari keadaan saat ini.