CARA MEMBUAT MESIN ABSTRAK FSA DAN GRAMMAR PADA TEORI BAHASA DAN AUTOMATA

Assalamu'alaikum warahamtullohi Wabarakatuh,

Pada blog kali ini saya Widia Rahayu Debora Namah akan memaparkan Tugas UAS membuat mesin abstrak :

1. Finite State Automata (FSA)
2. Grammar (TATA BAHASA)

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 

Nondeterministic Finite Automata (NFA) adalah salah satu bagian dari otomata berhingga atau Finite State Automata (FSA). Pada Nondeterministic Finite Automata (NFA) dimungkinkan satu simbol menimbulkan transisi ke lebih dari satu kondisi dan memberikan beberapa kemungkinan gerakan sehingga keluarannya tidak dapat dipastikan. Selain itu dimungkinkan juga terjadinya transisi spontan atau transisi –ε.

• Diagram 

Diagram FSA

• Penulisan Formal

•  Uji Input

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

Diagram Grammar

• Penulisan Formal

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

V = {S, A, B, C} 

T = {0, 1}

P = {S→ 1A|S→0A, A→1A, A→0B|B→0C, B→1C | C→0}

S = S

 

• Uji Input

 

Mohon maaf apabila ada kesalahan dalam pembuatan laporan ini. Semoga laporan ini dapat bermanfaat bagi para pembaca.

Sekian dan Terimakasih :)