Langsung ke konten utama

Bahasa Automata : Finite State Automata dan Grammar

1. Finite State Automata (FSA)

FSA didefinisikan sebagai pasanga 5 tupel yaitu : ( Q, Σ, δ, S, F)

Q = Himpunan state
Σ = himpunan hingga simbol input (alfabet)
δ = fungsi transisi, menggambarkan transisi state FSA akibat pembacaan simbol input.
S = State awal
F = State akhir

Untuk membuat diagram transisinya kita akan menggunakan aplikasi JFLAP. Setelah aplikasi JFLAP dibuka akan tampil beberapa menu, pilih menu Finite Automaton.


Setelah memilih menu Finite Automaton akan terbuka window baru yang berupa halaman kerja.
Langkah pertama untuk membuat diagram FSA adalah membuat state, untuk membuatnya klik tombol dengan icon huruf q yang dilingkari. kemudian klik di kotak putih untuk menempatkan state.
Setelah membuat state untuk menghubungkannya pilih tombol dengan icon anak panah, kemudain drag dari satu state ke state yang lain, jika akan membuat looping cukup klik di satu state, kemudian masukan parameter inputan di kotak yang muncul.
Tambahkan lagi beberapa state dan transition/inputan agar menjadi diagram yang diinginkan. Setelah selesai untuk menambahkan Start State dan Finish State klik kanan di state lalu akan muncul menu pilih Initial untuk membuat Start State dan pilih Final untuk membuat Finish State.

Setelah Diagram FSA jadi, sekarang kita akan menulis bahasa formlanya.


M = { Q,δ,Σ,S,F}
Q (himpunan state) = { q0,q1,q2,q3,q4,q5,q6,q7}
Σ (inputan) = {1,0}
S (start state) = {q0}
F (finish state) = {q7}


 Sekarang kita akan melakukan test menggunakan 5 input yang berbeda. untuk mengetesnya pilih menu input lalu pilih fast run unuk menjalankan satu input, dan multiple run untuk menjalankan beberapa input sekaligus. kali ini saya akan menggunakan multiple run, dengan hasil sebagai berikut.



2. Grammar

 Grammar (G) didefinisikan sebagai pasangan 4 tuple : Vt, Vn, S dan Q. dituliskan sebagai G(Vt,Vn,S,Q,), dimana :

 Vt = himpunan simbol-simbol terminal (atau himpunan token-token, atau alfabet)
Vn = Himpunan simbol-simbol non terminal
S = Simbol awal
Q = Himpunan produksi.

Untuk membuat diagram transisi  FSA menggunaka Grammar kita harus menentukan bahasa formalnya terlebih dahulu. Pertama kita masuk ke aplikasi JFLAP lalu pilih sub menu Grammar kemudian akan muncul jendela kerja Diagram Grammar.

Kita tentukan bahasa formalnya.


V = { S, V, W, X, Y, Z}

T = { a,b }
P = { S => aV|aY, V => bX|aZ, W => aY|bV, X => aZ|b, Y => a|bZ, Z => b|aW }
S = {S}

Lalu kita masukan ke aplikasi.


Setelah itu pilih sub menu Convert dan pilih Convert Right-Linear Grammar to FA


Setelah tampil jendela baru, klik tombol Show All untuk menampilkan diagram secara lengkap.

Sekarang kita akan menginputnya menggunakan 5 input  yang berbeda, dengan hasil sebagai berikut :



Baiklah itu saja yang bisa saya sampaikan, kurang lebihnya mohon maaf, Terima Kasih ....

Komentar

Posting Komentar

Postingan populer dari blog ini

Tutorial Normalisasi dari Struk ke Database

Assalamualaikaum warahmatullahi wabarakatuh Kali ini saya Dani Mulyana. Akan membagikan Tutorial Normalisasi dari Struk ke Database. Apa itu Normalisasi ? Normalisasi adalah suatu proses mendesain struktur Database agar sebagian besar ambigulity bisa dihilangkan sehingga bisa menghasilkan sebuah tabel Database yang normal atau tidak lebih teratur. Untuk Tutorial ini saya akan menggunakan Struk dari salah satu restoran, berikut adalah gambar Struk-nya. Untuk mengubah Struk ini menjadi Database yang benar diperlukan 3 tahapan Normalisasi. Ok, langsung saja kita lanjut ke tahapan yang pertama. 1.) 1 NF (Normalisasi Pertama) Pada tahapan pertama ini kita akan memasukan setiap data kedalam bentuk Flat File dan tidak boleh ada set atribut yang berulang-ulang. Berikut adalah Contoh Tahapan Pertama yang sudah saya buat : 2.) 2 NF (Normalisasi Kedua) Di tahap ini kita akan memisahkan Tabel Normalisasi Pertama menjadi beberapa tabel agar kita bisa menentukan Atribut Kunci Uta...
1 komentar
Baca selengkapnya

Mesin Moore dan Mesin Mealy

Assalamu'alaikum, pada kali ini saya akan memberi contoh pembuatan mesin moore dan Mesin Mealy  Mesin Moore Mesin Moore adalah finite-state machine yang outptnya berasosiasi dengan state, atau tertulis pada setiap state, sehingga jumlah state sama dengan jumlah output. Selain itu Mesin Moore tidak memiliki final state. Mesin Moore ditetapkan ke dalam 6 tuple yaitu sebagai berikut : M = {Q, å , d , S, D , l } Q = Himpunan State å  = Himpunan Input d  = Fungsi Transisi S = Simbol State Awal D  = Himpunan Output l  = Fungsi Output untuk Setiap State Contoh Soal Buatlah Mesin Moore untuk menentukan sisa pembagian atau modulus 7 dengan inputan berupa  biner ! Jawab : M = {Q, å ,  d , S,  D ,  l } Karna sisa hasil bagi 7 ada 6 maka outputnya adalah {0,1,2,3,4,5,6} Q = {q0,q1,q2,q3,q4,q5,q6} å  = {0,1} S = {q0} D  = {0,1,2,3,4,5,6} l (q0) = 0 |  l (q1) = 1 |  l (q2) = 2 |  l (q3) = 3 |  l ...
Posting Komentar
Baca selengkapnya

Project Java "Data Penerimaan Barang Bulanan"

Pada kesempatan kali ini saya akan mendekripsikan aplikasi yang telah saya buat untuk memenuhi tugas UAS. aplikasi ini bernama "Data Penerimaan Barang Bulanan". Aplikasi ini diperuntukan untuk gudang atau perusahaan cabang yang menerima kiriman barang dari pusat secara berkala perbulannya. berikut ini tampilan aplikasinya: Untuk database nya saya menggunakan mysql, untuk membuatnya, dengan format tabel sebagai berikut: Dan dengan flowchart sebagai berikut: Sekarang saya akan menjelaskan bagaimana aplikasi ini berjalan, pertama kita klik tombol/button Baru untuk memasukan data : Dengan sourcecode sebagai berikut: Setelah itu kita diharuskan mengisi semua kolom yang tersedia untuk data masukan ke database: Lalu kita klik  tombol Simpan untuk memasukan data yang telah kita input ke database: Dengan sourcecode tombol simpan sebagai berikut: Dan seperti yang terlihat, semua data yang telah kita input telah masuk ke database. untuk menghapus database kit...
Posting Komentar
Baca selengkapnya