Tito Satryo: Bahasa & Teori Automata

Bahasa & Teori Automata

Tito Satryo,01 Juli 2019

PENGERTIAN AUTOMATA

Teori Otomata adalah teori mengenai mesin-mesin abstrak, dan berkaitan erat dengan teori bahasa formal. ada beberapa hal yang berkaitan dengan Otomata, yaitu Grammar. Grammar adalah bentuk abstrak yang dapat diterima (accept) untuk membangkitkan suatu kalimat otomata berdasarkan suatu aturan tertentu.

FINITE STATE AUTOMATA (FSA)

Finite State Automata/state otomata berhingga, selanjutnya kita sebut sebagai FSA, bukanlah mesin fisik tetapi suatu model matematika dari suatu sistem yang menerima input dan output diskrit. Finite state automata memiliki state ke state lain. Perubahan state ini dinyatakan oleh fungsi transisi. Jenis otomata ini tidak memiliki tempat penyimpanan sehingga kemampuan ‘mengingatnya’ terbatas. Mekanisme kontrol pada suatu elevator / lift adalah contoh yang bagus untuk suatu otomata.

Mekanisme tersebut tidak ‘mengingat’ semua permintaan sebelumnya tetapi hanya posisi lift saat itu pada suatu lantai, pergerakan (keatas atau bawah). Dan sekumpulan permintaan yang belum terpenuhi. Dalam ilmu komputer kita akan menemui banyak contoh dari sistem finitestate automata. teori mengenai finitestate automata adalah suatu tool yang berguna untuk merancang sistem tersebut. Mekanisme kerja suatu finitestate automata bisa diaplikasikan pada analisis leksikal, text-editor, protokol komunikasi jaringan (misal protokol kermit), dan pendek pariti.

Berikut Contoh Soalnya:

FSA

FSA dinyatakan oleh 5 tuple M=(Q , Σ , δ , S , F )

Q = himpunan state

Σ = himpunan simbol input

δ = fungsi transisi δ : Q × ΣS ∈ Q

S = state awal / initial state ,

F = state akhir,F ⊆ Q

Q = {q0,q1,q2,q3,q4}

Σ = {0,1}

S = {q0}

F = {q3}

δ = (deskripsi dengan bentuk tabel)

ẟ	1	0
q0	-	Q2
q1	Q2	-
Q2	Q2,q3	Q1,q4
Q3	-	-
Q4	Q2	-

Ini adalah hasil dari inputnya

01011 = Accept

00110 = Reject

GRAMMAR

Grammar adalah bentuk abstrak yang dapat diterima (accept) untuk membangkitkan suatu kalimat otomata berdasarkan suatu aturan tertentu. Grammar (G) didefinisikan sebagai pasangan 4 tuple : V,T,P,S

V = Himpunan Variabel / Non Terminal

T = Himpunan Terminal

P = Himpunan Produksi

S = Simbol Awal / Start