TUGAS UAS MEMBUAT 2 MESIN ABSTRAK (FSA & GRAMAAR)

1. 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.

Bahasa yang paling sederhana adalah bahasa reguler (tipe 3). Mesin yang bisa mengenalinya adalah Finite Automata. Finite Automata adalah mesin komputasi. Pada bahasan ini mesin komputasi yang dimaksud adalah mesin abstrak bukan mesin fisik, namun memadai untuk diimplementasikan secara nyata.

Pengertian FSA

Finite Automata adalah model matematika sistem dengan masukan dan keluaran diskrit. Finite State Automata adalah model matematika yang dapat menerima inputan dan mengeluarkan output. Memiliki state berhingga banyaknya dan dapat berpindah dari satu ke yang lainnya sesuai dengan inputan dan fungsi transis.

Definisi formal FSA

Secara formal FSA dinyatakan dengan 5-tuple atau M =(Q, Σ, δ, q0, F):

1. Q = himpunan state/kedudukan

2. Σ = abjad, himpunan simbol input

3. δ = transition function/fungsi transisi

4. q0 ∈ Q = start state

5. F ⊆ Q = set of accept (or final) states

Contoh FSA :

Kita dapat menggambar secara formal dengan menulis M4 = (Q, Σ, δ, q0, F)), di mana:

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

2. Σ = {0,1}

3. δ =

δ	0	1
q0	-	q1
q1	q1	q4
q2	q0	-
q3	-	q2
q4	q3	q1,q2

4. q0 ∈ Q = {q1}

5. F ⊆ Q ={q1}

Disini lalu kita coba uji input FSA dengan menggunakan  Multipe Run :

Berikut yang saya buat mesin abstark Fsa dilemabar jawban

2. GRAMMAR

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

Definisi Formal Grammar

Grammar G didefinisikan sebagai pasangan 4 tuple : V , V , S, dan P, dan dituliskan sebagai G (V , V , S, P), dimana :

V : himpunan  simbol-simbol  terminal  (alfabet) àkamus

V : himpunan simbol-simbol non terminal

T : himpunan simbol terminal

P : himpunan produksi

S : simbol awal (atau simbol start)

Contoh Formal Grammar

Lalu disini kita coba uji coba:

Setelah  melakukan Uji coba Grammar, berikut konversi mesin abstrak diatas menjadi 4 tuple yaitu:

V= {S,A,B,C,d}
T = {0,1}
P= {S→0S, S→1A, S→0B, C→0C, A→1S, B→0C, C→1D, B→1S, B→λ, A→0D}
S= {q2}

Disini lalu kita coba uji input FSA dengan menggunakan  Multipe Run :

Berikut yang saya buat mesin abstrak grammar dilembar jawaban