UTS Bahasa Automata

Grammar

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

Definisi Formal FSA

Grammar G didefinisikan sebagai 4 tuple : G (V,T,P,S) ,dimana:

V : Himpunan Simbol Variabel

T : Himpunan Simbol Terminal

P : Himpunan Produksi 

S : Simbol awal(simbol start)

lalu kita uji coba grammar sebagai berikut :
1. pertama kita buka aplikasi JFLAP, lalu kita pilih Grammar

2. langkah selanjutnya lalu kita buat himpunan produksinya

3. langkah ke-3 kita convert to FA

lalu disini kita uji coba.
Contoh Formal FSA :

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

T : {0,1}

P : {S→0C,S→1A,B→1B, B→0D,B→1C,A→1D,D→λ, C→1D, A→0B,A→λ}

S : (Start)

Fungsi Transisi :

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

Σ : {0,1}

S : Start (q3)

F : Finish(q5)

δ : Fungsi transisi δ : Q x Σ

δ	0	1	λ
q0	Q1,q4	-	Q5
q1	Q4	Q1,q2,q4	-
q2	-	Q4	-
q3	Q2	Q0	-
q4	-	-	Q5
q5	-	-	-

lalu langkah selanjutnya kita buat Grammar convert to FSA ,dari contoh yg diatas kita buat.

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 Au fisik, namun memadai untuk diimplementasikan secara nyata.

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

1. Q = himpunan state/kedudukan

2. Σ = abjad, himpunan simbol input

3. δ = transition function/fungsi transisi

4. S = start state

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

Contoh FSA:

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

1.Q :  {q0,q1, q2, q3,q4,q5}

2.Σ : {0, 1}

3.δ : Fungsi transisi δ : Q x Σ

δ	0	1	λ
q0	Q1,q4	-	Q5
q1	Q4	Q1,q2,q4	-
q2	-	Q4	-
q3	Q2	Q0	-
q4	-	-	Q5
q5	-	-

4.S : Start(q3)

5.F : Finish {q5}

disini lalu kita uji input FSA dengan menggunakan Multipe Run :

Lampiran Jawaban :