FSA&Grammar Automata UAS

                Nama    : Muhammad Sidiq Jaelani Pangestu

                Kelas     : 05TPLM003

NIM       : 161021450502

1.      Pengertian Finite State Automata (FSA)

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 (FSA) adalah model matematika yang dapat menerima input dan mengeluarkan output yang memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasarkan input dan fungsi transisi. Finite state automata tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini.

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

Karakteristik Finite Automata

a.       Setiap Finite Automata memiliki keadaan dan transisi yang terbatas.

b.      Transisi dari satu keadaan ke keadaan lainnya dapat bersifat deterministik atau non-deterministik.

c.       Setiap Finite Automata selalu memiliki keadaan awal.

d.      Finite Automata dapat memiliki lebih dari satu keadaan akhir.
jika setelah pemrosesan seluruh string, keadaan akhir dicapai, artinya otomata menerima string tersebut.

Setiap FSA memiliki:

a.       Himpunan berhingga (finite) status (state)

- Satu buah status sebagai status awal (initial state), biasa dinyatakan q0.

- Beberapa buah status sebagai status akhir (final state).

b.      Himpunan berhingga simbol masukan.

c.       Fungsi transisi Menentukan status berikutnya dari setiap pasang status dan sebuah simbol masukan.

Mesin Abstrak FSA

Diagram :

Deskripsi format penulisan M({Q,Σ,δ,S,F}):

1.      Q = (q0,q1,q2,q3,q4,q5)                                               

2.      Σ = (0,1)

3.      δ = is described as

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

4.      S = q0 is the start

5.      F = q

Uji input :

2.      Pengertian Grammar

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

Mesin Abstrak Grammar

Tata bahasa Grammar di definisikan dengan 4 Tupel, G = ({V,T,P,S}) dimana :

V =Humpinan symbol variable / non terminal

T =Himpunan symbol terminal

P =kumpulan aturan produksi

S = Simbol awal

Jadi q2 = (S) lewat jalur b menuju q4 = (E) ditulis S => bE

Secara formal dapat ditulis :

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

T = {a,b}

P = { S => bE, E=> A| B, E => aA | b,A=> b| C=>a}

S = S (Start)