Grammar Otomata & Finite State Otomata

Grammar Otomata & Finite State Otomata

A. Grammar 

Konsep Dasar Grammar

Teori Otomata itu 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.

Grammar Memiliki 4 tuple : G : (V, T, P, S)

• V : Himpunan Simbol Variabel
• T : Himpunan Terminal
• P : Kumpulan aturan produksi
• S : State awal

Contoh Soal Grammar

Aturan Produksi 

Hasil convert to FA

Penjelasan dengan 4 tuple grammar : 

V         : A, B, C, D

T          : y, u, k, m, a, e, n, x

P          : A => yB
              B => uB
              B => k
              C => m
              A => e
              B => aC
              C => xD
              D => n

S          : q0

========================================================================

B. Finite State Otomata

Konsep dasar FSA 

Finite State Automata (FSA) adalah model matematika yang dapat menerima input dan mengeluarkan output yang memiliki state, berhingga banyaknya dan dapat perpindah dari satu state ke state lainnya berdasarkan input dan fungsi transisi.

Secara formal finite state automata memiliki 5 tuple : 

• Q : Himpunan State / Kedudukan
• Σ : Himpunan Simbol Input 
• δ : Fungsi Transisi
• S : State Awal / kedudukan Awal
• F : Himpunan State Akhir 

Contoh Soal FSA

Penjelasan 5 tuple Finite State Otomata :

Q         : q0, q1, q2, q3, q4

Σ         : y, u, k, m, a, e, n, x

δ          : 

       

S          : q0

F          : q4

Uji input string dari gambar FSA diatas :

========================================================================

Lampiran Jawaban :

Grammar

Konsep Dasar Grammar

Teori Otomata itu 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.

Grammar Memiliki 4 tuple : G : (V, T, P, S)

• V : Himpunan Simbol Variabel
• T : Himpunan Terminal
• P : Kumpulan aturan produksi
• S : State awal

       Simbol Terminal-

·       Simbol terminal adalah simbol yang merupakan konstituen dari kalimat yang dihasilkan menggunakan tata bahasa.

·       Simbol terminal dilambangkan dengan menggunakan huruf kecil seperti a, b, c dll.

Simbol Non-Terminal-

·       Simbol non-terminal adalah simbol yang mengambil bagian dalam pembuatan kalimat tetapi bukan bagian dari itu.

·       Simbol non-Terminal juga disebut sebagai simbol atau variabel tambahan .

·       Simbol non-terminal dilambangkan dengan menggunakan huruf kapital seperti A, B, C dll.


Contoh Soal

nl

b
       Pembahasan
     V         : A, B, C, D

T          : y, u, k, m, v, a, x

P          : A =>yB
              B=>uB
              B=>k
              C=>m
              A=>v
              B=>aC
              C=>xD
              D=>

S          : Q0

Finite State Automata (FSA)

Finite State automata

Finite State Automata (FSA) adalah model matematika yang dapat menerima input dan mengeluarkan output yang memiliki state, berhingga banyaknya dan dapat perpindah dari satu state ke state lainnya berdasarkan input dan fungsi transisi.

Secara formal finite state automata memiliki 5 tuple :

• Q : Himpunan State / Kedudukan
• Σ : Himpunan Simbol Input 
• δ : Fungsi Transisi
• S : State Awal / kedudukan Awal
• F : Himpunan State Akhir

Contoh Soal

1. Setiap Kelompok, buatlah FSA tersebut dalam bentuk formal yang terdiri dari 5 buah tuplel

Jawab 

M=(Q, Ʃ,S,F, δ)     Q={q0,q1,q2,q3}

Ʃ={0,1}

S=q0

F={q0}

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

2. Tentukan String berikut apakah diterima atau ditolak  :

• 1101 
• 0101
• 1001
• 1110
• 0001

Jawab 

Link Power Point 

https://drive.google.com/file/d/13SWJiFZqQi6arTLpThGKtXEAE54Elb98/view?usp=sharing