Uji Coba Mesin Abstrak Finite State Automata (FSA) & Grammar Convert to FA

~~Uji Coba Mesin Abstrak~~

~Finite State Automata (FSA) & Grammar Convert to FA~

Sebelum masuk ke uji coba, saya sudah membuat terlebih dahulu di kertas, seperti gambar di bawah ini.

1. Finite State Automata (FSA)

Finite State Automata adalah model matematika yang dapat menerima input dan mengeluarkan output yang memiliki state yang berpindah dari satu state ke state yang lainnya berdasarkan input dan fungsi transisi. Finite state automata tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini.

Secara formal FSA dinyatakan dengan 5-tuple atau M =(Q, Σ, δ, q0, F):
1. Q = himpunan state/kedudukan
2. Σ = abjad, himpunan simbol input
3. δ = transition function
4. q0 ∈ Q = start state/initial state
5. F ⊆ Q = final states

• Uji Coba Mesin Abstrak

Langkah awalnya jalankan software/aplikasi  JFLAP, lalu klik/buka Finite Automaton.

Lalu buatlah seperti gambar di bawah ini, dengan tools yg sudah di sediakan.

Dan selanjutnya saya akan menguji coba mesin abstrak tersebut dengan 5 uji input yg berbeda.

3 uji input yang pertama diuji melalui Multiple Run seperti gambar di bawah ini.

Lalu 2 uji input yg terakhir diuji melalui Step by State.

Step by State yg pertama :

Dan uji coba diatas hasilnya reject atau di tolak, karena tidak mencapai state finish.

Step by State yang kedua :

Uji coba diatas juga sama di tolak karena tidak mencapai state finish.

      2. Grammar Convert to FA

Tata Bahasa (Grammar) bisa didefinisikan secara formal sebagai kumpulan dari himpunan-himpunan variabel. Simbol-symbol terminal, symbol awal, yang dibatasi oleh aturan-aturan produksi. Pada tahun 1959, seorang ahli bernama Noam Chomsky melakukan penggolongan tingkatan Bahasa menjadi empat, yang disebut dengan hirarki Chomsky.

Secara umum tata Bahasa dirumuskan sebagai :

α → β, yang berarti α menghasilkan β atau α menurunkan β.

Di mana α menyatakan simbol-simbol pada ruas kiri aturan produksi (sebelah kiri tanda `→’) dan β menyatakan symbol-symbol pada ruas kanan aturan produksi (sebelah kanan tanda ` →’).

Simbol variabel/non terminal adalah simbol yang masih bisa diturunkan dan ditandai dengan huruf besar seperti A, B, C, dst.

Simbol terminal adalah simbol yang sudah tidak bisa diturunkan dan ditandai dengan huruf kecil seperti a, b, c, dst.

Secara formal Grammar dinyatakan dengan 4-tuple yaitu: V, T, P, dan S.

Yaitu : 

V = Himpunan Variable (Ditandai dengan huruf besar)

T = Himpunan terminal (Ditandai dengan huruf kecil)

P = Himpunan Produksi

S = State awal

• Uji Coba Mesin Abstrak

Langkah Awal sama seperti FSA buka aplikasi nya lalu masuk ke Grammar.

Dan masukkan lah produksi-produksi nya seperti gambar di bawah.

Lalu di convert menjadi FA pilih "Convert Right-Linear Grammar to FA

Dan hasilnya akan seperti gambar di bawah ini, klik show all untuk menampilkan Terminal nya.

Dan untuk menyusun state" nya supaya sama dengan yang saya buat di kertas, klik panah hitam

Lalu pindahkan state"nya seperti di gambar bawah ini.

Sekian dari uji coba mesin abstrak FSA dan Grammar convert to FA, jika ada kesalahan, kekurangan, mohon di maklumi.

~~Terima Kasih~~