Grammar & FSA

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 imput dan mengeluarkan output yang memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state yang lainnya berdasarkan input dan fungsi transisi.
   Finiti State Automata dinyatakab oleh pasangan 5 tuple yaitu :

Rumus: M = { Q, ∑, S, F, δ }

Q = State

∑ = Inputan yang ada

S = Inisial State

F = Final State

δ = Fungsi Transisi

Berikut gambar dari FSA yang saya buat:

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

∑ = { 1, 0 }

S = q0

F = q2

δ =

	1	0
q0	q1, q4	–
q1	–	10
q2	q3	q0
q3	q3	q2
q4	q4	q3

Hasil Inputan:

Digambar tersebut hasil inputan dari:

10110 = Accepted

0101110 = Rejected

Grammar

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

Grammar G didefinisikan sebagai pasangan 4 tuple : V , V , S, dan P, dan dituliskan sebagai G(V , V , S, P), dimana :

V : himpunan  simbol-simbol  terminal  (alfabet) àkamus

V : himpunan simbol-simbol non terminal

T : himpunan simbol terminal

p : himpunan produksi

S : simbol awal (atau simbol start)

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

T = { 1, 0 }

S = { S }

F = { E } { q5 }

P = { S -> 0B, S -> 1A, B -> 1C, C -> 0A, A -> 0D, D -> 0D, D -> 1, A -> 1 }

Hasil Inputan:

Digambar tersebut hasil inputan dari:

10110 = Reject

0101110 = Reject

0101 = Accepted