FINITE STATE AUTOMATA DAN NON FINITE STATE AUTOMATA

1.          FSA(Finite State Automata)

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 sturan tertentu yang dirumuskan sebagai suatu FUNGSI transisi M.

Karakteristik :

• 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).

Penerapan :

Secara formal FSA atau AH (Automata Hingga) dapat didefinisikan sebagai pasangan 5 Tupel atau TUPLE-5 : (K, VT, M, S, Z) atau M(inisial Tuple) = (Q, ∑, δ, S, F).

Dimana :

• K atau Q : himpunan hingga stata,
• VT atau ∑ (Sigma) : himpunan hingga simbol input (alfabet)
• M atau δ (Delta)  : fungsi transisi, menggambarkan transisi stata AH akibat pembacaan simbol input. (Fungsi transisi ini biasanya diberikan dalam bentuk tabel.)
• S ∈ K atau S ∈ Q : stata AWAL
• Z ⊆ K atau F ⊆ Q : himpunan stata penerima atau AKHIR

Contoh :

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 :

Cara kerja FSA :

Mula-mula dalam state S0

Jika dari S0 menerima 1 : akan ke State-S1

Jika dari S0 menerima 11 : akan ke State-S1 lalu ke S2

Jika dari S0 menerima 0 : akan tetap di State- S0

Jika dari S0 menerima 10 : akan tetap kembali lagi State- S0

Jika dari S0 berturut-turut menerima masukan : 111, maka ia akan kembali ke- S0

• 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 di notasikan 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* U 010* } = { ((0,1)11 U 01)0* }

• Ada dua jenis FSA :

Finite State Automata dapat berupa:

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.

2.          DFA(Deterministic Finite Automata)

Deterministic finite automata (DFA) --> M = (Q, ∑, δ, S, F),

dimana :

Q : himpunan state/kedudukan

∑ : himpunan simbol input

∂ : fungsi transisi,

dimana ∂ ∈ Q x ∑ --> Q

S : State awal (initial state)

F : himpunan state akhir (Final State)

Language --> L(M) : (x| ∂(S,x) di dalam F)

Contoh :

DFA F(K, V , 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 adalah sebagai berikut :

• Lambang stata awal adalah node dengan anak panah.

• Lambang stata 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 (stata 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 (stata 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 stata penerima) --> kalimat aaabbaba ditolak

Kesimpulan : sebuah kalimat diterima oleh DFA jika tracingnya berakhir di salah satu stata

penerima.

3.          NDFA(Non Deterministic Finite Automata)/NFA(Non Finite Automata)

Non Deterministic finite automata (NFA) --> M = (Q, ∑, δ, S, F),

dimana :

Q : himpunan state/kedudukan

∑ : himpunan simbol input

∂ : fungsi transisi, dimana ∂ ∈ Q x (∑ ⋃ ε) --> P(Q)

P(Q) : set of all subsets of Q

S : State awal (initial state)

F : himpunan state akhir (Final State)

Language --> L(M) : (x| ∂(S,x) di dalam F)

Contoh :

NFA (Q, ∑, δ, S, F). dimana :

Q = {q 0, q1 , q2 ,q3 , q4 }

δ diberikan dalam tabel berikut :

∑= {a, b,c}

S = q0

F = {q4}

Diagram atau Graf yang dapat dibuat :

L(M) = {aaa, ..., abab, ..., acbc, ...}

4.          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’), ..., (van, van’), yaitu pasangan terurut (stata DFA A, stata 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 dengan label 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 (van, van’) 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 atas maka dapat dibentuk tabel berikut,

Keterangan:

> (2, 5) adalah pasangan terurut baru

> (3, 6) adalah pasangan terurut baru

> (2, 7) adalah pasangan terurut baru

> tidak ada lagi pasangan terurut baru

5.          Reduksi Jumlah State pada FSA

Reduksi adalah Mengurangi jumlah state dengan tidak mengurangi kemampuannya semula untuk menerima suatu bahasa. State pada FSA dapat direduksi apabila terdapat useless state(jumlah otomata yang sedikit agar mempermudah pengerjaan). Hasil dari FSA yang direduksi merupakan ekuivalensi dari FSA semula. Sasaran kita di sini adalah mengurangi jumlah state dari suatu Finite State Automata, dengan tidak mengurangi kemampuannya semula untuk menerima suatu bahasa.

Ada dua buah istilah baru yang perlu kita ketahui yaitu :

            1. Distinguishable yang berarti dapat dibedakan.

            2. Indistinguishable yang berarti tidak dapat dibedakan.

Langkah :

• Hapuslah semua state yg 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 merupakanstate-state indistinguishable.
• Beberapa state yang indistinguishable dapat digabungkan menjadi satu state.
• Sesuaikan transisi dari state-state gabungan tersebut.

Contoh :

Pengerjaan :

Identifikasilah setiap kombinasi state yang mungkin :

1. Kombinasi state yang mungkin adalah :

• (q 0 , q1 )
• (q 0 , q 2 )
• (q 0 , q 3 )
• (q 0 , q 4 )
• (q1 , q 2 )
• (q1 , q 3 )
• (q1 , q 4 )
• (q 2 , q 3 )
• (q 2 , q 4 )
• (q 3 , q 4 )

2. State yang berpasangan dengan state akhir (q 4 ) merupakan state yang distinguishable

• (q 0 , q1 )
• (q 0 , q 2 )
• (q 0 , q 3 )
• (q 0 , q 4 ) : Distinguishable
• (q1 , q 2 )
• (q1 , q 3 )
• (q1 , q 4 ) : Distinguishable
• (q 2 , q 3 )
• (q 2 , q 4 ) : Distinguishable
• (q 3 , q 4 ) : Distinguishable

3. Untuk pasangan state yang lain jika masing-masing state mendapat input yang sama, maka bila satu state mencapai state akhir dan yang lain tidak mencapai state akhir maka dikatakan distinguishable.

Untuk (q 0 , q1 ) :

• δ (q 0 , 1) = q 3
• δ (q1 , 1) = q 4
• δ (q 0 , 0) = q1
• δ (q1 , 0) = q 2

Maka (q 0 , q1 ) : Distinguishable
Untuk (q 0 , q 2 ) :

• δ (q 0 , 1) = q 3
• δ (q 2 , 1) = q 4
• δ (q 0 , 0) = q1
• δ (q 2 , 0) = q1

Maka (q 0 , q 2 ) : Distinguishable
Untuk (q 0 , q 3 ) :

• δ (q 0 , 1) = q 3
• δ (q 3 , 1) = q 4
• δ (q 0 , 0) = q1
• δ (q 3 , 0) = q2

Maka (q 0 , q 3 ) : Distinguishable

Untuk (q1 , q 2 )

• δ (q1 , 1) = q 4
• δ (q 2 , 1) = q 4
• δ (q1 , 0) = q 2
• δ (q 2 , 0) = q1

Maka (q1 , q 2 ) : Indistinguishable

Untuk (q1 , q 3 )

• δ (q1 , 1) = q 4
• δ (q 3 , 1) = q 4
• δ (q1 , 0) = q 2
• δ (q 3 , 0) = q 2

Maka (q1 , q 3 ) : Indistinguishable

Untuk (q 2 , q 3 )

• δ (q 2 , 1) = q 4
• δ (q 3 , 1) = q 4
• δ (q 2 , 0) = q1
• δ (q 3 , 0) = q 2

Maka (q 2 , q 3 ) : Indistinguishable

4. Maka Didapatkan pasangan state sebagai berikut :

• (q 0 , q1 ) : Distinguishable
• (q 0 , q 2 ) : Distinguishable
• (q 0 , q 3 ) : Distinguishable
• (q 0 , q 4 ) : Distinguishable
• (q1 , q 2 ) : Indistinguishable
• (q1 , q 3 ) : Indistinguishable
• (q1 , q 4 ) : Distinguishable
• (q 2 , q 3 ) : Indistinguishable
• (q 2 , q 4 ) : Distinguishable
• (q 3 , q 4 ) : Distinguishable

5. Kelompokkan pasangan state yang indistinguishable :

• (q1 , q 2 ) : Indistinguishable
• (q1 , q 3 ) : Indistinguishable
• (q 2 , q 3 ) : Indistinguishable

6. Karena q1 indistinguishable dengan q2 dan q2 indistinguishable dengan q3 , maka bisa dikatakan bahwa q1 , q2 , dan q3 saling indistinguishable dan dapat dijadikan satu State.

7. Sehingga hasil penyederhanaannya adalah sebagai berikut :

_______________________________________________________________________________________________________________________

Daftar Pustaka

1. Materi Persentasi "Finite State Automata dan Non Finite State Automata" Dosen pengampu Teori Bahasa Automata Bapak Garno, M.Kom. Fakultas Ilmu Komputer Universitas Singaperbangsa Karawang.
2. https://docplayer.info/36555908-Teori-bahasa-dan-automata-finite-state-automata-non-finite-state-automata.html
3. http://lisetyo.staff.gunadarma.ac.id/Downloads/files/42312/TEORI+BAHASA+DAN+OTOMATA+PERTEMUAN+KE-3.pdf
4. https://www.scribd.com/doc/179155911/Reduksi-jumlah-state-pada-DFA
5. https://ocw.upj.ac.id/files/Slide-TIF202-Reduksi-jumlah-state-pada-finite-state-automata.pptx