Tugas Uts Fsa & grammar

Finite State Automata dan Grammar Automata dari Satu Mesin Abstrak

Pada artikel kali ini Kita akan membuat satu mesin Abstrak, yang kemudian dari mesin abstrak ini akan Kita definisikan kedalam 5 Tuple Finite State Automata (FSA) dan 4 Tuple Grammar Automata.

Langkah Langkah Membuat Mesin Abstrak
Berhubung kita akan membuat mesin abstrak menggunakan JFLAP maka pastikan Anda sudah menginstall aplikasi Java dan JFLAP, karena keduanya berkesinambungan.

Buka aplikasi JFLAP yang sudah terinstall, kemudian pilih grammar.

Inputkan himpunan produksinya.

Jika sudah, pada tool Convert pilih Convert Right Linier Grammar to FA. Kemudian klik Show All, maka akan muncul tampilan mesin Abstrak yang sudah dibuat.

FINITE STATE AUTOMATA
Finite state 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.

Secara Formal FSA dinyatakan dengan 5 tuple atau M = (Q, ∑, δ, S,F) dimana :

Q adalah himpunan state
∑ adalah himpunan input
δ adalah transition Function
S adalah State awal /initial state
F adalah State akhir

Definisi 5 tuple dari mesin abstrak

Q = {q0,q1,q2,q3,q4, q5}
∑ = {a,b, λ }
δ =

· S =q0

· F =q5

Uji input

Penjelasan : ika semua simbol yang kita input berhenti di Final State maka “Accepted/Diterima”, sebaliknya jika berhenti di State yang bukan merupakan Final State maka “Reject/Ditolak”.

· abbb artinya dari State q0 melalui terminal a ke state q4, kemudian dari state q4 melalui terminal b ke state q3, lalu dari state q3 melalui terminal b ke state q1. Kemudian dari state q1 melalui terminal b ke state akhir yaitu q5. Maka status “ACCEPTED”.

Begitupun seterusnya untuk uji input yang lain.

GRAMMAR AUTOMATA

Grammar adalah bentuk abstrak yang dapat diterima (accept) unttuk membangkitkan suatu kalimat otomata berdasarkan suatu aturan tertentu.

Grammar(G) didefinisikan sebagai pasangan 4 tuple (V,T,S,P)

V : Himpunan simbol simbol non terminal (Variabel)
T : Himpunan simbol simbol terminal, lamda (λ) tidak perlu dicantumkan
S : Simbol awal (start)
P : Himpunan Produksi