UAS Teori Bahasa dan Otomata

Contoh Mesin Grammar dan Mesin Mealy yang akan saya buat.

A. Mesin GRAMMAR
Grammar adalah Sebuah bentuk mesin abstrak yang dapat diterima ( Accept ) untuk membangkitkan suatu kalimat otomata berdasarkan aturan tertentu .

Grammar dinyatakan oleh 4 Tupple Yaitu :
G = (V,TS,P).

V = Himpunan Variabel (Huruf Besar)
T = Himpunan Terminal (Huruf Kecil)
S = State Awal
P = Himpunan Produksi

Langkah awal untuk membuat mesin Grammar adalah sebagai berikut:
1. Buka aplikasi Jflap lalu pilih Grammar

2. Selanjutnya masukan himpunan produksinya, kemudian isi pada kolom LHS dan RHS

3. Kemudian pilih convert, Convert Right-Liniar Grammar to FA

4. Setelah itu klik tombol show all dan hasil mesin abstraknya seperti ini

Berikut hasil tupplenya:
V = (S,A,B,C,D)
T = (a,b,c,d)
S = (q2)
P = S-aB, C-cA, B-aC, D-bC, A-aC, B-dA, D-cB, S-aD, C-λ

Langkah selanjutnya mesin abstrak  grammar dikonversikan ke definisi

Finite State Automata adalah Mesin abstrak berupa sistem model matematika dengan masukan dan keluaran  diskrit yang dapat mengenali bahsa paling sederhana dan dapat diimplementasikan  secara nyata.

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

Berikut ini contoh dari mesin abstrak FSA dan hasil tupple nya

Fungsi Transisi

Uji Input

B. Mesin Mealy

Mesin Mealy adalah finite-state machine yang nilai outputnya ditentukan oleh state dan inputnya.

Mesin Mealy adalah deterministic finite-state transducer, untuk setiap keadaan dan masukan, paling banyak satu transisi dimungkinkan. Diagram mesin mealy menghubungkan nilai output dengan masing-masing transisi.

Contoh Mesin Mealy

Mesin Mealy ditetapkan ke dalam 6 tuple yang terdiri dari: 

S = Himpunan State

S0 = State awal 

∑ = Himpunan input

∆ =  Himpunan output

T =  Fungsi Transisi

G = Fungsi output

Fungsi Transisi:

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

∑= 0,1

∆= {Y,T}

S= q0

λ= (q0,0)=T

λ= (q0,1)=T

λ= (q1,0)=Y

λ= (q1,1)=Y

λ= (q2,0)=T

λ= (q2,1)= -

λ= (q3,0)=T

λ= (q3,1)=Y

λ= (q4,0)=Y

λ= (q4,1)= -

λ= (q5,0)=Y

λ= (q5,1)=T

Sekian dan Terimakasih