Teori Bahasa dan Automata: Finite State Automata & Non Finite State Automata

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: