Mengkonversikan Grammars ke Finite State Otomata

A.Grammar

Grammar  adalah tata bahasa yang mempunyai tujuan sama seperti halnya tata bahasa regular yaitu merupakan suatu cara untuk menunjukkan bagaimana menghasilkan suatu untai-untai dalam sebuah bahasa

Regular Grammars dinyatakan oleh pasangan 4 tuple, yaitu:

        M= (V, T, S, P)

V = Variabel (menggunakan huruf kecil)

T = Terminal (menggunakan huruf besar)

S = Variabel Awal

P = Fungsi Transisi

Selanjutnya kita akan membuat Mesin Abstrak untuk Grammar di aplikasi JFLAP

1. Buka aplikasi JFLAP lalu pilih Grammar

2. Masukkan himpunan produksinya seperti gambar dibawah ini

3. Di menu Convert pilih Convert Right-Linear Grammar to FA

4. Setelah itu klik Show All, maka hasilnya akan seperti gambar di bawah ini

Sekarang kita akan melengkapi isian formal dari masing-masing tupelnya

V = { S, A, B, C, D}

T = {a, b}

S = S

P = { S→aA,  S→ aB,  A→ bC,  A→ aC,  B→ bD,  C→Bd, D→ aC , C→a ,  D→ b}

B. Finite State Otomata

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.

Finite State Automata dinyatakan oleh pasangan 5 tuple, yaitu:
M=(Q , Σ , δ , S , F )
Q = himpunan state
Σ = himpunan simbol input
δ = fungsi transisi δ : Q × Σ
S = state awal / initial state , S ∈ Q
F = state akhir, F ⊆ Q

Sekarang kita akan melengkapi isian formal dari masing-masing tupelnya

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

Σ = {a,b}

δ = fungsi transisi

S = {q2}

F = {q5}

Uji Input FSA :



1. aabaa  = Diterima
2. ababa  = Ditolak
3. baabb  = Ditolak
4. ababb  = Diterima
5. bbbaa  = Ditolak

*Lembar jawaban UTS