UAS MUHAMMAD SOBARI 161021450342 - DFA DAN GRAMMAR

Assalamu'alaikum warahmatullohi wabarakatuh

Alhamdulillahirobbil 'alamiin, telah diselesaikan laporan tugas untuk memenuhi nilai Ujian Akhir Semester V mata Kuliah Teori Bahasa dan Otomata. Adapun Tugasnya adalah membuat mesin Finite State Automata diantaranya Mesin DFA dan Grammar. Berikut uraiannya :

Pengertian Finite State Automata (FSA)

Finite State Automata (FSA) 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.

Contoh Sistem dengan state berhingga :
Sistem elevator
Mesin penjual minuman kaleng (vending machine)
Pengatur lampu lalu lintas
Sirkit switching di komputer dan telekomunikasi
Lexical Analyzer
Neuron Nets

Finite State Diagram (FSD)
Finite State Automata dapat dimodelkan dengan Finite State Diagram (FSD) dapat juga disebut State Transition Diagram.

Finite State Diagram terdiri dari:

1. Lingkaran menyatakan state
Lingkaran diberi label sesuai dengan nama state tersebut.

Adapun pembagian lingkaran adalah:
- Lingkaran bergaris tunggal berarti state sementara
- Lingkaran bergaris ganda berarti state akhir

2. Anak Panah menyatakan transisi yang terjadi
Label di anak panah menyatakan simbol yang membuat transisi dari 1 state ke state lain

1 anak panah diberi label start untuk menyatakan awal mula transisi dilakukan

Klasifikasi FSA
Ada dua jenis FSA :
•Deterministic finite automata (DFA) 
Terdiri dari 1 transisi dari suatu state pada 1 simbol masukan.

•Non deterministik finite automata.(NFA)
Lebih dari 1 transisi dari suatu state dimungkinkan pada simbol masukan yang sama

Kedua finite automata tersebut mampu mengenali himpunan reguler secara presisi. Dengan demikian kedua finite automata itu dapat mengenali string-string yang ditunjukkan dengan ekspresi reguler secara tepat.

1. Praktikum DFA

 Deterministic Finite Automata merupakan sebuah fungsi yang harus terdefinisi untuk semua pasangan state-input yang ada didalam Q X ∑. Deterministik finite automata (DFA) bersifat deterministik, yang berarti bahwa automata tersebut tidak dapat berada di lebih dari satu state pada saat yang bersamaan.

a.    Formal Definition Tuple

b.    Diagram FSA

c.    Uji Input

Untuk melakukan pengujian terhadap mesin NFA diatas, dilakukan 3 sample input yang berbeda,diantaranya :

- 11010 (Reject)

- 01101 (Accept)

- 111000 (reject)

2. Praktikum Grammar

Tata bahasa (grammar) bisa didefinisikan secara formal sebagai kumpulan dari

himpunan-himpunan variabel, simbol-simbol terminal, simbol awal, yang dibatasi oleh aturan-aturan produksi. Suatu tata bahasa (grammar) didefinisikan dengan 4 Tupel yaitu : V, T, P, dan S

Di mana,

V = Himpunan simbol variabel / non terminal

T = Himpunan simbol terminal

P = Kumpulan aturan produksi

S = Simbol awal

Definisi Formal

Secara formal tata bahasa yang diperoleh dari otomata adalah sebagai berikut.

V = {B,A,R,I}

T = {m,s}

P = { B → mA, B→s, A→sA, A→mI,I→sA, I→mR, R→sB, R→m}

S = B

Diagram Grammar

Uji Input Gammar