Teori Bahasa dan Automata
Finite State Automata & Non Finite State
Automata
Finite
state automata adalah mesin abstrak berupa sistem model matematika dengan
masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana
(bahasa reguler) dan dapat diimplementasikan secara nyata. Finite state
automata tidak memiliki tempat penyimpanan / memory, hanya bisa mengingat state
terkini.
Finite state automata dinyatakan oleh pasangan 5 Tuple, yaitu
:
M = (Q , Σ , δ , S , F )
Q =
Himpunan state
Σ (Sigma) =
Himpunan simbol input (alfabet)
δ (Delta) =
Fungsi transisi δ : Q × Σ
S =
State awal / initial state , S ∈ Q
F =
State akhir, F ⊆ Q
Karakteristik Finite Automata
1. Setiap
Finite Automata memiliki keadaan dan transisi yang terbatas.
2. Transisi
dari satu keadaan ke keadaan lainnya dapat bersifat deterministik atau
non-deterministik.
3. Setiap
Finite Automata selalu memiliki keadaan awal.
4. Finite
Automata dapat memiliki lebih dari satu keadaan akhir.
jika
setelah pemrosesan seluruh string, keadaan akhir dicapai, artinya otomata
menerima string tersebut.
Setiap FSA memiliki:
1.
Himpunan
berhingga (finite) status (state)
·
Satu
buah status sebagai status awal (initial state), biasa dinyatakan q0
·
Beberapa
buah status sebagai status akhir (final state).
2.
Himpunan
berhingga simbol masukan
3.
Fungsi
transisi
Menentukan status berikutnya dari setiap pasang status dan sebuah simbol
masukan.
Cara
Kerja Finite State Automata
Finite State Automata bekerja dengan cara mesin membaca memori masukan berupa
tape yaitu 1 karakter tiap saat (dari kiri ke kanan) menggunakan head baca yang
dikendalikan oleh kotak kendali state berhingga dimana pada mesin terdapat
sejumlah state berhingga.
Finite Automata selalu dalam kondisi yang disebut state awal (initial
state) pada saat Finite Automata mulai membaca tape. Perubahan state terjadi
pada mesin ketika sebuah karakter berikutnya dibaca. Ketika head telah sampai
pada akhir tape dan kondisi yang ditemui adalah state akhir, maka string yang
terdapat pada tape dikatakan diterima Finite Automata (String-string merupakan
milik bahasa bila diterima Finite Automata bahasa tersebut).
Finite State Diagram (FSD)
Finite State Automata dapat dimodelkan dengan Finite State Diagram (FSD)
dapat juga disebut State Transition Diagram. Sistem transisi adalah sistem yang
tingkah lakunya disajikan dalam bentuk keadaan-keadaan (states). Sistem
tersebut dapat bergerak dari state yang satu ke state lainnya sesuai dengan
input yang diberikan padanya.
Fungsi Transisi (δ) adalah representasi
matematis atas transisi keadaan.
Finite State Diagram terdiri dari:
·
Lingkaran
menyatakan state
Lingkaran diberi label sesuai dengan
nama state tersebut. Adapun pembagian lingkaran adalah:
·
Lingkaran
bergaris tunggal berarti state sementara
·
Lingkaran
bergaris ganda berarti state akhir
·
Anak
Panah menyatakan transisi yang terjadi.
Label di anak panah menyatakan simbol
yang membuat transisi dari 1 state ke state lain. 1 anak panah diberi label
start untuk menyatakan awal mula transisi dilakukan.
Contoh FSA : Pencek parity ganjil
Misal
input : 1101
Genap —1— Ganjil —1— Genap — 0 — Genap — 1 — Ganjil (berakhir pada ganjil) : Sehingga
“1101” diterima mesin.
Misal input : 1100
Genap — 1 — Ganjil — 1 — Genap — 0 — Genap — 0 — Genap (berakhir pada genap) : Sehingga
“1100” ditolak mesin.
Dari
contoh diatas, maka:
Q = {Genap, Ganjil}
Σ = {0,1}
S = Genap
F = {Ganjil}
atau
δ (Genap, 0) = Genap
δ (Genap, 1) = Ganjil
δ (Ganjil, 0) =
Ganjil
δ (Ganjil, 1) = Genap
FSA dibentuk dari
lingkaran yang menyatakan state:
·
Label pada lingkaran adalah nama state.
·
Busur menyatakan transisi/ perpindahan.
·
Label pada busur yaitu symbol input.
·
Lingkaran yang didahului sebuah busur tanpa label menyatakan
state awal
·
Lingkaran ganda menyatakan state akhir/ final.
Jadi sebuah mesin
otomata dapat dinyatakan dalam diagram transisi, fungsi transisi dan tabel
transisi.
Jenis Finite State Automata (FSA)
Ada dua jenis FSA :
1.
Deterministic Finite Automata (DFA)
Artinya : Dari suatu state ada tepat satu state berikutnya
untuk setiap simbol input yang diterima.
2.
Non-deterministic Finite Automata (NDFA)
/ NFA
Artinya : Dari suatu state bisa terdapat 0,1 atau lebih busur
keluar (transisi) berlabel simbol input yang sama.
Deterministic
Finite Automata (DFA)
Q = Himpunan state /
kedudukan
Σ (Sigma) = Himpunan simbol input (alfabet)
δ (Delta) = Fungsi transisi δ : Q × Σ
S = State awal / initial
state
F = State akhir / final state
Language ➝ L (M)
: ( x | δ (S,x) di dalam F)
Contoh 1 :
Pengujian
untuk menerima bit string dengan banyaknya 0 genap, serta banyaknya 1 genap.
Diagram
transisinya :
DFA nya :
Q = {q0 , q1 , q2 ,
q3}
Σ = {0,1}
S = q0
F = {q0}
Fungsi transisi :
Input : 0011
Maka tracking :
δ (q0,011) = δ (q2,11) = δ (q3,1) = q2 ⇒ Karena q2 termasuk dalam state akhir, maka “0011” berada dalam L(M)
Input : 10010
Maka tracking :
δ( q0,1010) = δ(
q1,010) = δ( q3,10) = δ( q2,0) = q0 ⇒ Karena q0 tidak termasuk dalam state
akhir, maka “10010” tidak berada dalam L(M)
Contoh 2 :
Diagram transisinya :
DFA nya :
Q = {q0 , q1 , q2}
Σ = {a,b}
S = q0
F = { q2}
Fungsi transisi :
δ( q0,a) = q0
δ( q0,b) = q1
δ( q1,a) = q1
δ( q1,b) = q2
δ( q2,a) = q1
δ( q2,b) = q2
Input : abb
Maka tracking :
δ( q0,abb) = δ( q0,bb)
= δ( q1,b) = q2 ⇒ Karena q2 termasuk dalam state akhir, maka “abb” berada
dalam L(M)
Input : baba
Maka tracking :
δ(q0,baba) = δ(q1,aba)
= δ(q1,ba) = δ(q2,a) = q1 ⇒ Karena q1 tidak termasuk dalam state akhir,
maka “baba” tidak berada dalam L(M)
Non-deterministic
Finite Automata (NDFA) / NFA
Q = Himpunan state /
kedudukan
Σ (Sigma) = Himpunan simbol input (alfabet)
δ (Delta) = Fungsi transisi, dimana δ Î Q × (Σ ∪ ε ) ➝ p(Q)
S = State awal / initial
state
F = State akhir / final state
Language ➝ L (M)
: ( x | δ (S,x) di dalam F)
Contoh :
Berikut ini sebuah contoh NFA (Q, Σ, δ, S, F) dimana : Q = {q0, q1, q2, q3, q4}
δ diberikan dalam
tabel berikut :
Σ = {a, b, c}
S = q0
F = {q4}
Sebuah kalimat di terima NFA jika:
Salah satu trackingnya berakhir di
state akhir atau himpunan state setelah membaca string tersebut mengandung
state akhir
Telusurilah, apakah kalimat-kalimat
berikut diterima NFA di atas :
ab, abc, aabc, aabb
Jawab:
δ (q0 ,ab) ⇒ δ (q0,b) ∪ δ (q1 ,b) ⇒ {q0, q2} ∪ {q1} = {q0 , q1 , q2}
Himpunan state tidak mengandung state
akhir ⇒ kalimat ab tidak diterima
δ (q0 ,abc) ⇒ δ( q0 ,bc) ∪ δ (q1 ,bc) ⇒ {δ(q0 ,c) ∪ δ(q2 ,c)} ∪ δ (q1 , c)
{{ q0 , q3 }∪{ q2 }}∪{
q1 } = {q0 , q1 , q2 ,q3 }
Himpunan state tidak mengandung state
akhir ⇒ kalimat abc tidak diterima
Ekuivalensi Antar Deterministic Finite Automata
Dua DFA M1 dan M2 dinyatakan ekivalen
apabila L(M1) = L(M2)
Reduksi
Jumlah State pada FSA
· Reduksi dilakukan untuk mengurangi jumlah state
tanpa mengurangi kemampuan untuk menerima
· State pada 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
Reduksi Jumlah State pada FSA - 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
Reduksi Jumlah State pada FSA – 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 :
Sebuah Mesin DFA
·
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 :
- 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.
- 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 :
Semoga artikel ini
dapat membantu dalam memahami tentang Finite State Automata & Non Finite State
Automata. Mohon maaf bila ada salah penulisan. Karena kesalahan hanya milik
manusia dan kebenaran hanya milik Allah SWT. Terima kasih ☺️
Daftar Pustaka :
Materi 7 Finite
State Automata & Non Finite State Automata Dosen pengampu Teori Bahasa dan Automata : Garno, M.Kom Fakultas Ilmu Komputer Universitas Singaperbangsa Karawang.
riskasimaremare.wordpress.com. Finite State Automata diakses melalui
docplayer.info. Teori Bahasa dan Automata Finite State Automata & Non Finite State Automata. Diakses melalui https://docplayer.info/36555908-Teori-bahasa-dan-automata-finite-state-automata-non-finite-state-automata.html
Tidak ada komentar:
Posting Komentar