FINITE STATE MACHINE / AUTOMATA

BAHASA FORMAL

Dapat dipandang sebagai entitasabstrak, yaitu sekumpulan string yang berisi simbol-simbol alphabet

Dapat juga dipandang sebagai entitas-entitas abstrak yang dapat dikenali ataudibangkitkan oleh mesin komputasi

Mesin komputasi yang sesuai untuk kelas

bahasa ini

Finite State Machine / Automata

FINITE AUTOMATA

Mesin abstrak berupa sistem modelmatematika dengan masukan dan keluarandiskrit yang dapat mengenali bahasasederhana dan dapat diimplementasikansecara nyata.

FINITE AUTOMATA

Model matematika/graf yang dapatmenerima input dan mengeluarkan output

Memiliki state yang berhingga banyaknya dan dapatberpindah dari satu state ke state lainnya berdasarinput dan fungsi transisi

Tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini.

Mekanisme kerja dapat diaplikasikan pada : elevator, text editor, pencek parity.

(Q, ∑, δ, S, F)FSA / FSM Didefinisikan oleh 5 tupel :

FINITE STATE AUTOMATA

Q : himpunan hingga state

∑ : himpunan hingga simbol input (alfabet)

δ : fungsi transisi, menggambarkan transisi state FSA akibatpembacaan simbol input.(Fungsi transisi ini biasanya diberikan dalam bentuk tabelatau representasi lainnya.)

S : state AWAL (Start)F : himpunan state AKHIR (Final)

Finite State Automata dapat dimodelkan dengan Finite State Diagram (FSD) dapat juga disebut State Transition Diagram.

FINITE STATE DIAGRAM

Lingkaran bergaris tunggal berartistate sementara

Lingkaran bergaris ganda berarti state akhir

1. Lingkaran menyatakan stateLingkaran diberi label sesuai dengan nama state tersebut.

Adapun pembagian lingkaran adalah:

2. Anak Panah menyatakan transisi yang terjadi

Label di anak panah menyatakan simbolyang membuat transisi dari 1 state ke state lain

1 anak panah diberi label start untukmenyatakan awal mula transisi dilakukan

Contoh:

FSA untuk mengecek parity angka 1 biner ganjil

Q ={Genap, Ganjil} himpunan state∑ ={0,1} himpunan simbol inputδ = fungsi transisi

S = Genap StartF = {Ganjil} Final state(ingat untuk himpunan harus ditulis di dalam {} )

input : 1101 diterima mesin

input : 1100 ditolak mesin

input : 1011 diterima mesin

input : 11011 ditolak mesin

Genap

Genap

Ganjil

Ganjil

Maka:

Q = {Genap, Ganjil}

δ = {0,1}S = GenapF = {Ganjil}

Tabel Transisi:

δ (Genap,0) = Genapδ (Genap,1) = Ganjilδ (Ganjil,0) = Ganjilδ (Ganjil,1) = Genap

Jenis Finite State Automata

1.Deterministic Finite Automata (DFA) otomata berhingga yang pasti (tetap/tertentu)

dari suatu state ada tepat satu state berikutnyauntuk setiap simbol masukan yang diterima

2. Non-deterministic Finite Automata (NFA)

dari suatu state ada 0, 1 atau lebih state berikutnya untuk setiap simbol masukan yang diterima

otomata berhingga yang tidak pasti

Untuk NFA harus dicoba semua kemungkinanyang ada sampai terdapat satu yang mencapaistate akhir.

Deterministic Finite Automata (DFA)

Pada DFA dari suatu state ada tepat satu state berikutnya untuk setiap simbol input (masukan) yang di terima

Contoh : pengujian parity ganjil

Contoh lain : Pengujian untuk menerima bit string dengan banyaknya 0 genap, serta banyaknya 1 genap.

Pengujian untuk menerima bit string denganbanyaknya 0 genap, serta banyaknya 1 genap.

Diagram transisi-nya:

0011 : diterima.

10010 : ditolak, karena banyaknya 0 ganjil

DFA nyaQ = {q0 , q1 , q2 , q3 }δ = {0,1}S = q0F = { q0}

Fungsi Transisi

δ ( q0,011)= δ ( q2,11) = δ ( q3,1)= q2

Ditolak

δ ( q0,1010)= δ ( q1,010) = δ ( q3,10)= δ ( q2,0)= q0

Diterima

011

1010

Non-deterministic Finite Automata (NFA)

Perbedaan dengan DFA: fungsi transisi dapat memiliki 0 atau lebih fungsi transisi untuk setiap simbol inputan

Untuk NFA harus dicoba semua kemungkinan yang ada sampai terdapat satu yang mencapai state akhir.

String diterima NFA bila terdapat suatu urutan transisi berdasar input, dari state awal ke state akhir.

Contoh :

G = ({q0 , q1 , q2 , q3, q4 }, {0,1}, δ , q0 , { q2 , q4}}

Q = {q0 , q1 , q2 , q3, q4 }δ = {0,1}S = q0F = { q2, q4 }

Fungsi Transisi

Contoh : string 01001 Diterima

Reduksi FSAPasangan State

Distinguishable & Indistinguishable

Dua buah state dari FSA disebut indistinguishable (tidak dapat dibedakan)

apabila :δ (q,w) Є F sedangkan δ (p,w) Є F dan

δ (q,w) Є F sedangkan δ (p,w) Є F untuk semua w Є ∑ */

/

Dua buah state dari FSA disebut distinguishable

(dapat dibedakan) bila terdapat w Є ∑* sedemikian hingga:

δ (q,w) Є F sedangkan δ (p,w) Є F danδ (q,w) Є F sedangkan δ (p,w) Є F untuk semua w Є ∑ */

/

Prosedur Menentukan Pasangan Status Indistinguishable

1. Hapus semua state yang tak dapat dicapai daristate awal.

2. Catat semua pasangan state (p,q) yang distinguishable, yaitu {(p,q) | p Є F q Є F}

3. Untuk setiap pasangan (p,q) sisanya, buatlah tabel state dengan mengecek setiap pasangan satu persatu

/

Contoh

1. Hapus state yang tidak tercapai -> tercapai semua2. Pasangan distinguishable (q0,q4), (q1,q4), (q2,q4),

(q3,q4).3. Pasangan sisanya (q0,q1), (q0,q2), (q0,q3), (q1,q2)

(q1,q3) (q2,q3)

Prosedur Reduksi DFA

1. Tentukan pasangan status indistinguishable.

2. Gabungkan setiap group indistinguishable state ke dalam satu state dengan relasi pembentukan group secara berantai : Jika p dan q indistingishable dan jika q dan r indistinguishable maka p dan r indistinguishable, dan p,q serta r indistinguishable semua berada dalam satu group.

3. sesuaikan transisi dari dan ke state-state gabungan.

Contoh:

1. pasangan status indistinguishable (q1,q2), (q1,q3) dan (q2,q3).

2. q1,q2,q3 ketiganya dapat digabung dalam satu state q123

3. Menyesuaikan transisi, sehingga DFA menjadi

EKUIVALENSI NFA-DFA

Algoritma :

1. Buat semua state yang merupakan subset dari state

semula

2. Telusuri transisi state–state yang baru terbentuk,

dari diagram transisi.

3. Tentukan state awal : {q0}

4. Tentukan state akhir adalah state yang elemennya

mengandung state akhir.

5. Reduksi state yang tak tercapai oleh state awal.

6. Rename nama-nama state yang tersisa.

Ubahlah NFA berikut menjadi DFA

Contoh :

M= {{q0,q1}, {0,1}, δ, q0,{q1}}

Jawab :

tabel transisi

Q = {q0 , q1}δ = {0,1}

S = q0F = { q1 }

1. State yang akan dibentuk : {}, {q0} {q1},{q0,q1}

2. Telusuri state

3. State awal : {q0}

4. State akhir yang mengandung q1, yaitu {q1},{q0,q1}

Diagram transisi-nya:

0 1

q0 {q1,q2} {}

q1 {} {q0,q1}

q2 {q1} {q1}

•Diket: M={{q0,q1 ,q2}, {0,1}, , q0,{q1}} dengan tabel transisi sbb. Ubahlah NFA berikut menjadi DFA

SEKIAN………….