Penjelasan Finite State Automata

Asssalamualaikum Warrahmatullahi Wabarrakatuh

Halo semuaa !!.....👋😊

Selamat datang di blog saya, perkenalkan saya Rina Setiyaningsih dengan NIM 202131022 , Mahasiswi Informatika dan berkuliah di Institut Teknologi PLN Jakarta.

Disini saya akan membahas ulang materi yang sudah disampaikan Bu DINE TIARA KUSUMA ,S.T., M.Kom. pada pertemuan di hari Rabu, 12 April 2023, materi yang disampaikan adalah pembahasan tentang teori Finite State Automata.

Finite State Automata

• FSA(Finite State Automata) merupakan tool yang sangat berguna dalam perancangan 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
• FSA atau AH(Automata Hingga) didefinisikan sebagai pasangan 5 tupel 

• Mesin ini memiliki 6 state : (q₀,q₁,q₂,q₃,q₄,q₅)
• State awal q₀
• Sedangkan q₃ dan q₄ adalah state akhir, dan
• Symbol input adalah (a,d,u)

 

CONTOH FINITE STATE AUTOMATA

Contoh : FSA untuk mengecek parity ganjil

Tabel transisi 

       Diagram Transisi

Definisi Formal FSA

FSA Terbagi 2:

1.     Deterministic (DFA)

2.     Non deterministic (NFA)

Deterministic (DFSA/DFA)

• Pada setiap input, hanya ada satu keadaan (state) tujuan dari keadaan saat ini.

Non- Deterministik (NFSA/NFA)

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

Notasi Lain DFA

1.     Diagram Transisi/ State Diagram

• Tiap keadaan merupakan simpul
• Tiap keadaan q e Q dan tiap symbol a e S, dituliskan sebagai d (q,a) = p. Artinya, diagram transisi memiliki panah dari ke 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 Transis

• 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 d (q,a)

CONTOH DFA

Contoh DFA yang dapat menerima string berakhir 01

CONTOH DFA 1 :

Jika M diberi input aabba, dengan state awal (q₀,aabba), maka :

(q₀, aabba)

(q₀,abba)

(q₀,bba)

(q₁,ba)

(q₀,a)

(q₀,e)

Karena ( q₀, aabba) , (q₀,e), jadi aabba diterima oleh M (Mesin DFA)

CONTOH DFA 2 : 

Contoh: diberikan input pada mesin DFA 110111, lakukan tracer 

 (q_{0 ,} 110111)

(q_{0 ,} 10111)

(q_{0 ,} 0111)

(q_{1 ,} 111)

(q_{1 ,} 11)

(q_{1 ,} 1)

(q_{1 ,} e)

Karena berhenti bukan di q_2, maka 110111 tidak diterima oleh mesin DFA.

CONTOH DFA 3:

Contoh : diberikan input pada mesin DFSA 10110, lakukan tracer :

(q_0, 10110)

(q_0, 0110)

(q_1, 110)

(q_1, 10)

(q_1, 0)

(q_2, e)

Karena berhenti di q_2, maka 10110 diterima oleh mesin DFSA

CONTOH DFA 4 : 

Contoh : diberikan string 011 dan 1010, buktikan bahwa string tersebut diterima atau ditolak !

(q₀, 011) = (q₂,11) = (q_3,1) = q₂ Ditolak

(q₀, 1010) = (q₂, 010) = (q₃, 10) = (q₂, 0) = (q₀,e) Diterima

Berikut pembahasaan materi pada 12 April 2023 .Sekian yang bisa saya sampaikan, Mohon maaf bila ada salah pengetikan.

Terimakasih, Sampai bertemu di penyampaian materi berikutnya👐😊

Wassalamualaikum Warrahmatullahi Wabarrakatuh