FINITE STATE AUTOMATA

 Pengertian FSA 

    FSA (Finite State Automata) merupakan tool yang sangat berguna dalam perancangan lexical analyzer, yaitu bagian dari kompilator yang mengelompokan karakter-karakter ke dalam sebuah token, yang berupa unit terkecil seperti nama, variabel, dan keyword. FSA dipakai untuk penganalisa leksikal text editor, pemrosesan text, dan program file-searching.

FSA atau AH (Automata Hingga) didefinisikan sebagai pasangan 5 tupel → M = (Q, 𝞢, 𝞭, S, F) 
Q : himpunan hingga state
𝞢 : himpunan hingga simbol input (alfabet)
𝞭 : fungsi transisi, menggambarkan transisi state FSA akibat pembacaan simbol input.

fungsi transisi ini biasanya diberikan dalam bentuk tabel.
S 𝟄 Q : state AWAL
F ⊆ Q : himpunan state AKHIR



◾ Mesin ini memiliki 6 state : (q0, q1, q2, q3, q4, q5).
◾ State awal q0,
◾ Sedangkan q3 dan q4 adalah state akhir, dan
◾ Simbol input adalah (a, d, u)

Contoh Finite State Automata

Contoh : FSA untuk mengecek parity ganjil
- Q = {Gnp, Gjl}
- 𝞢 = {0,1}
- S = Gnp
- F = Gjl

Jenis FSA

Deterministik (DFSA/DFA)
Pada Setiap input, hanya ada satu keadaan (state) tujuan dari keadaan saat ini.

Non - Deterministik (NFSA/NFA)
pada setiap input terdapat lebuh dari satu keadaan tujuan dari keadaan saat ini

Deterministic Finite Automata (DFA)
DFA, terdiri atas 5 tuple, yaitu :
A = (Q, 𝞢, 𝞭, q0, F)

Notasi Lain DFA

1. Diagram Transisi/State Diagram
    - Tiap keadaan merupakan kesimpulan
    - Tiap keadaan q 𝟄 Q dan tiap simbol a 𝟄 𝞢, dituliskan sebagai 𝞭(q,a) = p. Artinya, diagram
      transisi memiliki panah dari q ke p, yang berlabel a.
    - Keadaan awal (q₀) ditandai dengan adanya panah tanpa sumber
    - Simpul yang menjadi keadaan final ditandai dengan lingkaran bergaris tepi ganda
2. Tabel Transisi
    - Representasi daftar dari suatu fungsi
    - Baris menunjukan keadaan dan kolom menunjukan input
    - Isi dari baris menunjukan keadaan q dan isi dari kolom input a menunjukan keadaan 𝞭(q,a)

Contoh DFA

Contoh DFA yang dapat menerima string berakhiran 01
A = ({q₀, q₁, q₂}, {0,1}, 𝞭, q₀, {q₂}) dengan fungsi transisi 𝞭 diberikan dalam bentuk table :



Komentar

Posting Komentar

Postingan populer dari blog ini

DERET FOURIER

Gambar
Deret Fourier Deret Fourier adalah perluasan fungsi periodik f(x) dalam jumlah sinus dan cosinus yang tak terhingga. Deret Fourier memanfaatkan hubungan ortogonalitas fungsi sinus dan kosinus. Deret Laurent menghasilkan Deret Fourier Hal yang sulit untuk dipahami dan/atau dimotivasi adalah kenyataan bahwa fungsi periodik sembarang memiliki representasi deret Fourier. Pada bagian ini, kami membuktikan bahwa fungsi analitik periodik memiliki representasi seperti itu menggunakan ekspansi Laurent. Catatan : Untuk mencari deret Fourier, cukup menghitung integral yang menghasilkan koefisien a  0  , a  n  , dan b  n  dan memasukkannya ke dalam rumus deret besar. Biasanya, f(x) akan terdefinisi sedikit demi sedikit. Keuntungan besar deret Fourier dibandingkan deret Taylor: fungsi f(x) dapat mempunyai diskontinuitas. Rumus Deret Fourier Rumus deret fourier fungsi f(x) pada interval [-L, L], yaitu -L ≤ x ≤ L diberikan oleh: Contoh : Tentukan deret Fourier dari fungsi...
Baca selengkapnya

PENGINTEGRALAN FUNGSI RASIONAL

Gambar
Pengintegralan Fungsi Rasional Mengintegralkan fungsi rasional merupakan salah satu keterampilan penting dalam kalkulus. Fungsi rasional adalah fungsi yang dapat dinyatakan sebagai rasio (pecahan) dari dua polinomial. Dalam panduan ini, kita akan membahas teknik-teknik utama yang digunakan untuk mengintegralkan fungsi rasional. 1. Decomposisi Pecahan Parsial Decomposisi pecahan parsial adalah metode yang digunakan untuk memecah fungsi rasional menjadi jumlah pecahan yang lebih sederhana yang lebih mudah diintegralkan. 2. Pengintegralan Fungsi Sederhana Setelah fungsi rasional dipecah menjadi pecahan parsial, langkah selanjutnya adalah mengintegralkan masing-masing pecahan parsial tersebut 3. Teknik Lanjutan Selain dekomposisi pecahan parsial, ada beberapa teknik lanjutan yang dapat digunakan untuk mengintegralkan fungsi rasiona Contoh Faktor penyebut Tulis pecahan persial Sehingga, A + B = 2 2 𝐴 − 3 𝐵 = 1 2 A − 3 B = 1 Di peroleh,
Baca selengkapnya

FUNGSI DUA PEUBAH

Gambar
Fungsi Dua Peubah f Fungsi f merupakan fungsi dua peubah jika  f f  memetakan pasangan dua buah bilangan real  ( x , y ) ∈ D f ⊆ R 2 ( x , y ) ∈ D f ⊆ R 2  ke suatu bilangan real  f ( x , y ) f ( x , y ) . Himpunan  D f D f  disebut dengan domain atau daerah asal fungsi dan himpunan semua nilai  f ( x , y ) f ( x , y ) , dengan  ( x , y ) ∈ D f ( x , y ) ∈ D f  disebut dengan daerah hasil (range)  f f , dan dinotasikan dengan  R f R f  (Gambar 1). Jika daerah asal fungsi tidak diperinci, kita ambil D berupa daerah asal mulanya (natural domain), yakni himpunan semua titik  ( x , y ) ( x , y )  pada bidang di mana aturan fungsi berlaku dan menghasilkan suatu bilangan riil. Diperhatikan bahwa untuk mempelajari fungsi dua peubah, terlebih dahulu diharapkan dapat mempelajari sifat-sifat bilangan real dan fungsi satu peubah.   Contoh 1: Dalam bidang xy, buatlah grafik daerah asal mula untuk Penyelesaian: Agar atur...
Baca selengkapnya