TEORI BAHASA DAN OTOMATA FINITE STATE AUTOMATA (FSA)
Finite State Automata Sebuah Finite State Automata adalah: Model matematika yang dapat menerima input dan mengeluarkan output Kumpulan terbatas (finite set) dari state (kondisi/keadaan). Satu diantaranya menjadi initial state (kondisi awal) atau start state, dan beberapa (bisa berarti tidak ada) dari antaranya dinyatakan sebagai final state Himpunan alphabet berisi beberapa huruf, dimana string-string bentukan dari alphabet akan dibaca huruf demi huruf
Finite Automata Lanjt..
Kumpulan terbatas dari transition yang menjelaskan untuk tiap state dan tiap huruf yang dibaca ke state mana perjalanan dilanjutkan berdasarkan input dan fungsi transisi Tidak memiliki tempat penyimpanan atau memory, sehingga hanya bisa mengingat state terkini Mekanisme kerja dapat diaplikasikan pada: elevator, text editor, analisa leksikal, pen-cek-an parity
Contoh 1
Alphabet yang digunakan hanya 2 huruf, a dan b Ada 3 buah state, yaitu x, y dan z Aturan trasition yang dipakai adalah: 1. 2. 3. 4. 5.
Dari state Dari state Dari state Dari state Dari state
x x y y z
dan input a menuju state y dan input b menuju state z dan input a menuju state x dan input b menuju state z dan input apa saja tetap di state z
Ditentukan juga x sebagai start state dan z sebagai final state
Contoh 1 Lanjt..
Perhatikan apa yang akan terjadi bila string aaa diumpankan ke FA tersebut Penelusuran akan dimulai dari start state: Huruf pertama adalah a, sesuai aturan-1 akan menuju state y Huruf kedua adalah a, sesuai aturan-3 akan menuju state x Huruf ketiga adalah a, sesuai aturan-1 akan menuju state y String sudah diumpankan semua, tapi tidak mencapai final state Jadi, string aaa bukanlah termasuk di dalam bahasa yang didefinisikan oleh FA
Contoh 1 Lanjt..
Contoh lain, bila string abba diumpankan ke FA tersebut Hasilnya, perjalanan mencapai pada state z (final state) Jadi, string abba termasuk word dalam bahasa yang didefinisikan oleh FA tersebut
Contoh 1 Lanjt.. (Transition Table )
Tidak sulit menerka word apa saja yang diterima oleh FA tersebut, yaitu stringnya harus berisi minimal sebuah b agar mencapai state z Dari transition rule di atas, dapat dibuatkan sebuah transition table seperti di bawah ini:
State Start x y Final z
a y x z
b z z z
FA dapat dianggap sebagai suatu mesin. Ada suatu pergerakkan, perpindahan dari sebuah state ke state lain, karena adanya sebuah input
Contoh 1 Lanjt.. (Transition Diagram )
FA yang digambarkan dalam bentuk grafis Tanda (-) untuk start state dan (+) untuk final state Bentuk lain, start state memakai panah dan final state memakai lingkaran ganda a
a
x-
y
x
y a
a
b
a
b
b z+
b z
b a
b
Contoh 2 a
+ b
a, b
a
+
a, b
b
2 busur atau lebih yang berasal dari state yang sama dan menuju ke state yang sama pula dapat disatukan seperti gambar di atas Sekilas terkesan bahwa FA di atas dapat menerima string dalam bentuk apapun Namun, bila inputnya adalah null string (), maka tidak akan terjadi perpindahan state Jadi language yang diterima oleh mesin di atas adalah: ( a + b ) ( a + b )* = ( a + b )+
Contoh 3
Ada kemungkinan sebuah FA tidak akan menerima language apapun a
a, b
b a,b
a,b
a,b
+
Contoh 4 2 a
a a, b
1-
4+
a
b
b
b 3
Apa yang terjadi bila diberi input string ababa dan babbb (bagaimana pergerakkannya) ?
Contoh 4 Lanjt..
Transisi bila diberi input string ababa δ(1,a) = (2) δ(2,b) = (3) δ(3,a) = (2) δ(2,b) = (3) δ(3,a) = (2)
Contoh 4 Lanjt..
Transisi bila diberi input string babbb δ(1,b) = (3) δ(3,a) = (2) δ(2,b) = (3) δ(3,b) = (4) δ(4,b) = (4)
Tuple Pada FSA
Finite State Automata dinyatakan oleh 5 tuple, yaitu: M=(Q , Σ , δ , S , F )
Q = Himpunan state Σ = Himpunan simbol input δ = Fungsi/tabel transisi δ : Q × Σ S = State awal / initial state , S ∈ Q F = State akhir, F ∈ Q
Contoh 5 (Pen-cek Parity Ganjil)
Misal input : 1101 δ(Genap,1)=(Ganjil); δ(Ganjil,1)=(Ganjil); δ(Ganjil,0)=(Genap); δ(Genap,1)=(Ganjil) Result: Diterima mesin Misal input : 1100 δ(Genap,1)=(Ganjil); δ(Ganjil,1)=(Ganjil); δ(Ganjil,0)=(Genap); δ(Genap,0)=(Genap) Result: Ditolak mesin
Contoh 5 Lanjt.
Tuple pada contoh 5: Q = {Genap, Ganjil}; Σ = {0,1}; S = {Genap}; F = {Ganjil}
δ
0 1 Genap Genap Ganjil Ganjil Genap Ganjil Penjabaran tabel transisi di atas adalah: δ(Genap,0) = {Genap} δ(Genap,1) = {Ganjil} δ(Ganjil,0) = {Genap} δ(Ganjil,1) = {Ganjil}
Jenis FSA
Deterministic Finite Automata (DFA) Dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima Non-deterministic Finite Automata (NFA) Dari suatu state ada 0, 1 atau lebih state berikutnya untuk setiap simbol masukan yang diterima
DFA
(Deterministic Finite Automata)
Perhatikan !! Contoh 5 : Pengujian parity ganjil Contoh 6 : Pengujian untuk menerima bit string dengan banyaknya “0” genap, serta banyaknya “1” genap. 0011 : String diterima 10010 : String ditolak, karena “0” banyaknya berjumlah ganjil
Contoh 6 (DFA Lanjt..)
Diagram transisi
Contoh 6 Lanjt..
DFA tuple-nya Q = {q0, q1, q2, q3}; Σ = {0,1}; S = {q0}; F = {q0} δ (Tabel transisi) δ 0 1 q0 q2 q1 q1 q3 q0 q2 q0 q3 q3 q1 q2 Contoh string inputan: δ(q0,011)=δ(q2,11)=δ(q3,1)=q2 (Ditolak) δ(q0,1010)=δ(q1,010)=δ(q3,10)=δ(q2,0)=q0 (Diterima)
Contoh 7
Variabel dalam bahasa pascal diawali oleh huruf (besar/kecil), dan diikuti dengan huruf atau angka.
Latihan 1. Buatlah Tuple dari Diagram FSA dibawah ini:
2. Buatlah Tuple dan Diagram FSA dari pen-cek parity genap !
