Blog Teori Bahasa Dan Otomata tentang Finite State Otomata || Siti Nurul Maghfirah L_ 202131125

 

                                                                      Institute Teknologi PLN Jakarta

                                                            Dosen : Dine Tiara Kusuma S.T., M.Kom

Finite State Otomata

FSA (Finite State Automata) merupakan tool yang sangat berguna dalam perancangan lexical analyzer, yaitu bagian dari kompilator yang mengelompokkan 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.

FSA atau AH (Automata Hingga) didefinisikan sebagai pasangan 5 tupel yaitu, M = (Q, ∑, δ, S, F).

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 adalah state akhir, dan
• Simbol input adalah (a,d,u)

Contoh Finite State Automata untuk Mengecek Parity Ganjil

Keterangan :

• Q = [Gnp,Gjl]
• Σ= [0,1]
• S = Gnp
• F = Gjl

Definisi Formal Finite State Automata

Definisi Formal FSA

M = (Q, Σ, δ, S, F), dimana :

Q : Himpunan state

Σ : Abjad, Himpunan simbol input (masukan)

δ : Fungsi transisi, δ : Q x Σ => Q

S ∈ Q : State awal (Initial State)

F ⊆ Q : Himpunan state akhir (Final State)

Finite State Automata (FSA), yaitu Deterministic Finite Automata (DFA / DFSA) dan Non-Deterministic Finite Automata (NFA / NFSA).

·       Deterministic Finite Automata (DFA / DFSA) : Pada setiap input, hanya ada satu keadaan (state) tujuan dari keadaan saat ini.

·       Non-Deterministic Finite Automata (NFA / NFSA) : Pada setiap input terdapat lebih dari satu keadaan tujuan dari keadaan saat ini.

Deterministic Finite Automata (DFA / DFSA) terdiri atas 5 tupel, yaitu A = (Q, Σ, δ, Q0, F)

Notasi Lain Deterministic Finite Automata (DFA / DFSA) :

1. Diagram Transisi (State Diagram)

·       Tiap keadaan merupakan simpul,

·       Tiap keadaan q ∈ Q dan tiap simbol a ∈ Σ , dituliskan sebagai δ(q,a) = p. Artinya, diagram transisi memiliki panah dari q ke p, yang berlabel a,

·       Keadaan awal (q0) ditandai dengan adanya panah tanpa sumber,

·       Simpul yang menjadi keadaan final ditandai dengan lingkaran bergaris tepi ganda.

2. Tabel Transisi

·       Representasi daftar dari suatu fungsi,

·       Baris menunjukkan keadaan dan kolom menunjukkan input,

·       Isi dari baris menunjukkan keadaan q dan isi dari kolom input a menunjukkan keadaan δ(q,a).