UAS FSA DAN GRAMMAR

- Juli 09, 2019

Grammar (Tata Bahasa)

Tata bahasa (grammar) bisa didefinisikan secara formal sebagai kumpulan dari

himpunan-himpunan variabel, simbol-simbol terminal, simbol awal, yang dibatasi oleh

aturan-aturan produksi

Suatu tata bahasa (grammar) didefinisikan dengan 4 Tupel yaitu : V, T, P, dan S

Di mana,

V = Himpunan simbol variabel / non terminal

T = Himpunan simbol terminal

P = Kumpulan aturan produksi

S = Simbol awal

Diagram Grammar

Penulisan Formal

Secara formal tata bahasa yang diperoleh dari otomata adalah sebagai berikut.

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

T = {a, b}

P = { S → bA, S→ aB, B→ aE, B→ bC, B→ a, E→ a, E→ bB, E→ bC, E→ aE, E→ S, A→ B, A→ bA, A→ a }

S = S

Uji Input

Berdasarkan hasil dari langkah di atas maka akan didapat hasil sebagai berikut :

INPUT : abba : ACCEPT

INPUT : aaba : ACCEPT

INPUT : bbab : REJECT

INPUT : aabb : REJECT

FSA (Finite State Automata)

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

Diagram