A.
Penerapan Finite State Automata (FSA)
·
Model matematika
suatu sistem yang menerima input dan output diskrit
·
Mesin automata
dari bahasa Regular.
· Tidak memiliki
tempat penyimpanan sehingga kemampuan mengingat terbatas (contoh: elevator/lift).
·
Aplikatif -berguna
untuk merancang sistem nyata.
· Aplikasi
meliputi : analisis leksikal, text-editor, protokol komunikasi jaringan
(kermit) dan parity checker (pengecek parity).
Finite State Machine dapat berupa suatu mesin yang
tidak memiliki output. Finite State Machine yang tidak mengeluarkan output ini
dikenal sebagai Finite State Automata (FSA).
Pada FSA mesin mula-mula dalam state S0 dan menerima
sederatan masukan yang dapat mengubahnya ke state-state berikutnya. Dalam FSA juga
dikenal himpunan state-state tertentu yang disebut sabagai FINAL STATE.
Perubahan dari satu state ke state berikutnya mengikuti aturan tertentu yang
dirumuskan sebagai suatu FUNGSI transisi M.
Secara formal FSA dapat didefinisikan sebagai TUPLE-5
: (K, Vt, M, S, Z)
Dimana:
K : Himpunan
hingga state,
Vt : Himpunan
hingga simbol input (alfabet)
M
: Fungsi transisi, menggambarkan
transisi state AH akibat pembacaan simbol input. (Fungsi transisi ini biasanya diberikan
dalam bentuk tabel.)
S Î
K : State awal
Z Í
K : Himpunan state penerima / himpunan
state akhir
Ada dua jenis Finite State Automata :
· Deterministic
Finite Automata (DFA) : Transisi state AH akibat pembacaan sebuah simbol bersifat
tertentu. “Jika pada setiap state dari FSA tersebut apabila menerima input sebuah simbol maka HANYA ada SATU NEXT STATE yang
mungkin dituju.”
M (DFA) : K ´
Vt ® K
· Non
Deterministik Finite Automata (NDFA) : transisi stata AH akibat pembacaan
sebuah simbolbersifat tak tentu. “Jika FSA tersebut menerima input simbol maka
minimal ada satu state yang akan berpindah ke LEBIH DARI SATU NEXT STATE yang mungkin
dituju.”
M (AHN) : K ´
Vt ® 2^K
Contoh FSA :
Buatlah diagram transisi dari FSA yang
didefinisikan sebagai :
M =
(K, Vt, M, S, Z) dimana :
S =
{S0, S1, S2, S3}
Vt = {
0,1 }
K =
{S0, S3}
Dengan fungsi transisi M ada pada tabel
transisi sebagai berikut :
Diagram Transisi
FSA
Sebagai Pengenal String
Mesin FSA tersebut jika menerima masukan sederetan simbol dari simbol-simbol
yang diijinkan maka akan menuju suatu state tertentu. Jika state akhir yang
ditempuh setelah suatu FSA menerima sederetan simbol adalah state FINAL, maka
deretan simbol (string) tersebut dikatakan DIKENALI oleh FSA, atau dengan kata lain
FSA mengenali string tersebut. String yang dikenali oleh FSA merupakan suatu
BAHASA yang dikenali oleh FSA tersebut. Jika dimiliki FSA M maka bahasa yang
dikenali oleh FSA dinotasikan sebagai :
L (M) = { x | x semua string yang mengantar M dari S0 ke (Si Î Z) }
Untuk mesin FSA pada contoh :
L (M) = { 0* , 0*(10)0* , 0*(110,111)0* }
Contoh :
Tentukan bahasa L (M) yang dikenali oleh Mesin M berikut ini :
Jawab:
Dari diagram terlihat bahwa final-state adalah S3.
Pergerakan state yang mengantar ke final-state adalah S0 → S1 → S2 → S3 yakni
string : 011 atau string 111 yang dapat ditulis sebagai (0,1)11.
Pergerakan yang lain adalah dari S0 langsung ke S2 yaitu :
S0 → S2 → S3 yang
dilakukan melalui string : 01 Setelah berada pada final state masih ada pergerakan
yang bersifat rekursif pada S3 yaitu apabila diberikan masukan 0,00,000,… atau
: 0*.
Dengan demikian jika seluruh string tersebut digabungkan akan
menjadi : (0,1)110*U 010*, sehingga bahasa yang dikenali adalah:
L (M) = {(0,1)110*U010*} = {((0,1)11U01)0*}
B.
Deterministic Finite Automata
Berikut ini sebuah contoh DFA F (K, Vt, M, S, Z), dimana :
K = {q0, q1, q2}
Vt = {a, b}
S = q0
Z = {q0, q1}
M diberikan dalam tabel berikut :
Ilustrasi graf untuk
DFA F adalahsebagai berikut :
·
Lambang state awal adalah
node dengan anak panah.
·
Lambang state awal adalah
node ganda.
Telusurilah, apakah
kalimat-kalimat berikut diterima DFA : abababaa, aaaabab, aaabbaba.
Jawab:
M (q0,abababaa) Þ M (q0,bababaa) Þ
M (q1,ababaa) ÞM
(q0,babaa)
Þ M (q1,abaa) Þ
M (q0,baa) Þ
M (q1,aa) Þ
M(q0,a) Þ
q0
Tracing berakhir di q0 (state penerima) Þ kalimat abababaa diterima
M
(q0,aaaabab) Þ M (q0,aaabab) Þ
M (q0,aabab) Þ
M (q0,abab)
Þ
M (q0,bab) Þ
M (q1,ab) Þ
M (q0,b) Þ q1
Tracing berakhir di q1(state penerima)
kalimat aaaababa diterima
M
(q0,aaabbaba) Þ M (q0,aabbaba) Þ
M (q0,abbaba) Þ
M (q0,bbaba)
Þ
M (q1,bbaba) Þ
M (q2,baba) Þ
M (q2,aba) Þ
M (q2,ba)
Þ
M (q2,a) Þ
q2
Tracing berakhir di q2 (bukan state penerima) Þ kalimat aaabbaba ditolak
Kesimpulan : sebuah
kalimat diterima oleh DFA jika tracingnya berakhir di salah satu state penerima.
C.
Ekuivalen Antar DFA
Dua buah DFA dikatakan equivalen jika keduanya dapat menerima
bahasa yang sama. Misalkan kedua DFA tersebut adalah A dan A’. Misalkan pula
bahasa yang diterima adalah bahasa L yang dibangun oleh alfabet Vt = {a1, a2,
a3, ..., an}. Berikut ini algoritma untuk menguji equivalensi dua buah DFA.
1. Berikan nama kepada
semua stata masing-masing DFA dengan nama berbeda. Misalkan nama-nama tersebut
adalah : S, A1, A2, ... untuk DFA A, dan : S’, A1’, A2’, ... untuk DFA A’.
2. Buat tabel (n+1) kolom,
yaitu kolom-kolom : (v, v’), (va1,va1’), ..., (vna, vna’), yaitu pasangan
terurut (state DFA A, state DFA A’).
3. Isikan (S, S’) pada
baris pertama kolom (v, v’), dimana S dan S’ masing-masing adalah stata awal masing-masing
DFA.
4. Jika terdapat edge dari
S ke A1 dengan label a1 dan jika terdapat edge dari S’ ke A1’ juga denganlabel
a1, isikan pasangan terurut (A1, A1’) sebagai pada baris pertama kolom (va1,va1’)
Lakukan hal yang sama untuk kolom-kolom berikutnya.
5. Perhatikan nilai-nilai
pasangan terurut pada baris pertama. Jika terdapat nilai pasangan terurut pada
kolom (va1,va1’) s/d (vna, vna’) yang tidak sama dengan nilai pasangan terurut
(v, v’), tempatkan nilai tersebut pada kolom (v, v’) baris-baris berikutnya.
Lakukan hal yang sama seperti yang dilakukan pada langkah (4). Lanjutkan dengan
langkah (5).
6. Jika selama proses di
atas dihasilkan sebuah nilai pada kolom (v, v’), dengan komponen v merupakan stata
penerima sedangkan komponen v’ bukan, atau sebaliknya, maka kedua DFA tersebut
tidak ekuivalen. Proses dihentikan.
7. Jika kondisi (6) tidak
dipenuhi dan jika tidak ada lagi pasangan terurut baru yang harus ditempatkan
pada kolom (v, v’) maka proses dihentikan dan kedua DFA tersebut ekuivalen.
Contoh :
Periksalah ekuivalensi
kedua DFA berikut :
Jawab : Dengan
menggunakan menggunakan algoritma di atasmaka dapat dibentuk tabel berikut,
Keterangan:
·
(2, 5) adalahpasangan
terurut baru
·
(3, 6) adalahpasangan
terurut baru
·
(2, 7) adalahpasangan
terurut baru
·
Tidak ada lagipasangan
terurut baru
D.
Non Deterministic Finite Automata
Berikut ini sebuah contoh DFA F (K, Vt, M, S, Z), dimana :
K = {q0, q1, q2,
q3, q4, q5}
Vt = {a, b, c}
S = q0
Z = {q4}
M diberikan dalam tabel berikut :
Ilustrasi graf untuk NFA F adalah sebagai berikut:
Fungsi transisi M sebuah NFA dapat diperluas sebagai berikut :
·
M (q, ε)
= {q} untuk setiap q Î
K
·
M (q, t T) = È M (pi, T) dimana t ÎVt, T adalah Vt*, dan M (q, t) = {pi}
·
M ({q1, q2, ..., qn} , x)
= È M (qi, x), untuk x Î Vt*
Sebuah kalimat diterima NFA jika:
salah satu tracing-nya berakhir di stata penerima, atau himpunan
stata setelah membaca string tersebut mengandung state penerima.
Contoh :
Telusurilah, apakah kalimat-kalimat berikut diterima NFA : ab, aabc,
aabb
Jawab :
M (q0, ab) Þ M (q0, b) È
M (q1, b) Þ
{q0, q2} È
{q1} = {q0, q1, q2}
Himpunan state tidak
mengandung state penerima Þ kalimat ab tidak
diterima
M (q0, aabc) Þ M (q0, abc) È
M (q1, abc)
Þ {M (q0, bc) È
M (q1, bc)} È
M (q1, bc)
Þ {{M (q0, c) È
M (q2, c)} È
M (q1, c)} È
M (q1, c)
Þ {{{q0, q3} È
{q2}} È
{q1}} È
{q1} = {q0, q1, q2, q3}
Himpunan state tidak mengandung state penerima Þ kalimat aabc tidak diterima
M (q0, aabb) Þ M (q0, abb) È
M (q1, abb)
Þ {M (q0, bb) È
M(q1, bb)} È
M (q1, bb)
Þ {{M (q0, b) È
M (q2,b)} È
M (q1, b)} È
M (q1, b)
Þ {{{q0, q2} È
{q2, q4}} È
{q1}} È
{q1} = {q0, q1, q2, q4}
Himpunan state tidak mengandung state penerima Þ kalimat aabb diterima
NFA dengan Transisi Hampa
Perhatikan NFA berikut
:
NFA di atas mengandung
ruas dengan bobot ε. NFA demikian dinamakan NFA dengan transisi ε, atau
singkatnya NFA- ε. NFA- ε diatas menerima bahasa L = {1^i 0^j | i, j ≥ 0}
E.
Reduksi Jumlah State pada FSA
· Reduksi dilakukan untuk
mengurangi jumlah state tanpa mengurangi kemampuan untuk menerima suatu bahasa
seperti semula (efisiensi).
· Statepada FSA dapat
direduksi apabila terdapat useless state.
· Hasil dari FSA yang
direduksi merupakan ekivalensi dari FSA semula.
Pasangan State dapat
dikelompokkan berdasarkan:
· Distinguishable State
(dapat dibedakan) Dua state p dan q dari suatu DFA dikatakan indistinguishable apabila:
δ (q, w) Î F dan δ (p, w) Î F atau δ (q, w) ∉ F
dan δ (p,w) ∉ F untuk semua w Î
S*
· Indistinguishable State
(tidak dapat dibedakan) Dua state p dan q dari suatu DFA dikatakan distinguishable
jika ada string w Î
S* hingga:
δ (q,w) Î F dan δ (p,w) ∉ F
Relasi
Pasangan dua buah state memiliki salah satu kemungkinan distinguishable
atau indistinguishable tetapi tidak kedua-duanya. Dalam hal ini terdapat sebuah
relasi :
Jika p dan q
indistinguishable,
Dan q dan r indistinguishable
Maka p, r indistinguishable dan p, q, r
indistinguishable
Dalam melakukan eveluasi state, didefinisikan suatu relasi :
Untuk Q yg merupakan himpunan semua state
·
D adalah
himpunan state-state distinguishable,
dimana D Ì
Q
·
N adalah himpunan state-state
indistinguishable, dimana N Ì
Q
·
maka x Î N jika x Î Q dan x ∉ D
Step
· Hapuslah semua state yang
tidak dapat dicapai dari state awal (useless state).
· Buatlah semua pasangan state
(p, q) yang distinguishable, dimana p Î
F dan q Ï F.
Catat semua pasangan-pasangan state tersebut.
· Cari state lain yang
distinguishable dengan aturan : “Untuk semua (p, q) dan semua a Î ∑,
hitunglah δ (p, a) = pa dan δ (q, a) = qa. Jika pasangan (pa, qa) adalah pasangan
state yang distinguishable maka pasangan (p, q) juga termasuk pasangan yang
distinguishable.
· Semua pasangan state yang
tidak termasuk sebagai state yang distinguishable merupakan state-state indistinguishable.
· Beberapa state yang
indistinguishable dapat digabungkan menjadi satu state.
· Sesuaikan transisi dari
state-state gabungan tersebut.
Contoh :
· State q5 tidak dapat
dicapai dari state awal dengan jalan apapun (useless state). Hapus state q5
· Catat state-state distinguishable,
yaitu :
q4 Î F
sedang q0, q1, q2, q3 Ï
F sehingga pasangan (q0, q4) (q1, q4)
(q2, q4) dan (q3, q4) adalah distinguishable.
· Pasangan-pasangan state
lain yang distinguishable diturunkan berdasarkan pasangan dari langkah 2, yaitu
:
1.
Untuk pasangan (q0, q1)
δ (q0, 0) = q1 dan δ (q1,
0) = q2 → belum teridentifikasi
δ (q0, 1) = q3 dan δ (q1,
1) = q4 → (q3, q4) distinguishable maka (q0, q1) adalah distinguishable.
2.
Untuk pasangan (q0, q2)
δ (q0, 0) = q1 dan δ (q2,
0) = q1 → belum teridentifikasi
δ (q0, 1) = q3 dan δ (q2, 1) = q4 → (q3, q4) distinguishable maka
(q0, q2) adalah distinguishable.
· Setelah diperiksa semua
pasangan state maka terdapat state-state yang distinguishable :
(q0,q1), (q0,q2),
(q0,q3), (q0,q4), (q1,q4), (q2,q4), (q3,q4) Karena berdasarkan relasi-relasi
yang ada, tidak dapat dibuktikan (q1, q2), (q1, q3) dan (q2, q3)
distinguishable, sehingga disimpulkan
pasangan-pasangan state tersebut indistinguishable.
· Karena q1
indistinguishable dengan q2, q2
indistinguishable dengan q3, maka dapat disimpulkan q1, q2, q3 saling
indistinguishable dan dapat dijadikan satu state.
· Berdasarkan hasil
diatas maka hasil dari DFA yang
direduksi menjadi:
Sumber :
Nama :
Shania Risky Agustin
NPM :
1810631170097
Kelas : 4C
