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

Membuat Aplikasi Konversi Android Sederhana Versi 2

Assalamu'alaikum, kali ini saya akan membagikan cara untuk membuat aplkasi konversi android, berbeda dengan sebelumnya yang hanya ada 2 konversi yaitu koversi system number dan panjang. Kali ini akan ada 4 konversi dengan penambahan konversi berat dan suhu. Selain itu sekarang juga ada form login saat pertamam membuka aplikasi. Pertama-tama kita cari file String.xm yang berada di floder rsc>value>String.xml, lalu masukan input seperti gambar dibawah ini Kemudian kita mulai membuat halaman login, kita jadikan main-activity nya sebagai login form dengan  source code di file xml nya adalah sebagai berikut :  Dan isi file javanya sebegai berikut : Sekarang kita buat activity baru untuk menu, di file xml nya masukan source code sebagai berikut : Kemudian di file javanya masukan source code seperti dibawah ini : Sekarang kita buat activity baru lagi untuk activity konversi system number, di file xml nya masukan file sebagai berikut : Dan di...
Posting Komentar
Baca selengkapnya