Deterministic Finite Automata

CSG3D3 | Teori Komputasi

Deterministic Finite Automata

Agung Toto Wibowo Ahmad Suryan Yanti Rusmawati Mahmud Dwi Sulistiyo Kurniawan Nur Ramadhani Said Al Faraby Dede Rohidin

KK Intelligence, Computing, and Multimedia

Finite Automata Finite Automata (FA) : – Suatu model komputer dengan jumlah memory yang sangat terbatas. – Model komputasional yang paling sederhana.

Ada 2 jenis : – Deterministik Finite Automata (DFA)  “Deterministik”  setiap input alphabet/simbol dari suatu state hanya akan bertransisi ke satu state lain.

 Atau dengan kata lain, “deterministik” berarti tidak ambigu dalam menentukan next state.

– Non-Deterministik Finite Automata (NDFA)  “Non-Deterministrik”  setiap input alphabet/simbol dari suatu state mungkin akan bertransisi ke lebih dari satu state lain. Teori Komputasi | CSG3D3

Contoh Deterministic FA Mesin Genap di pertemuan sebelumnya (catatan: 0 adalah genap). Lihat bahwa dari q0, tidak ada kerancuan jika menerima input 0 (akan ke q1), dan sebagainya.

Teori Komputasi | CSG3D3

Contoh Non-Deterministic FA Mesin di bawah adalah mesin (NFA) untuk mengenali string biner yang selalu diakhiri 01. Lihat bahwa, dari state q0 akan muncul kerancuan atau keambiguan jika menerima input 0 (akan ke q0 atau q1).


Ilustrasi Mesin DFA

Input Tape

Head

Arah Pergerakan

State Indicator

1 4

2 3 Teori Komputasi | CSG3D3

Definisi DFA [1] Mesin automata yang terdiri dari finite number of state. Salah satu state sebagai intitial state. Minimal satu state menjadi accepted/final state. Mesin akan menerima input stream berupa simbol/alphabet yang akan diproses secara sekuensial. Mesin akan berubah dari state satu ke state yang lain berdasarkan simbol input dan current state.


Definisi DFA [2] Deterministic  mesin tidak diperkenankan ambigu. Finite menyatakan fakta bahwa mesin terdiri dari state yang jumlahnya finite (terbatas). Esensi DFA adalah string recognizer (menerima atau menolak sebuah string) berdasarkan definisi bahasa dari DFA tersebut. DFA juga dimungkinkan dapat menerima string kosong. Jika hal ini terjadi, maka initial state juga merupakan accepted state.


Definisi Formal DFA Sebuah finite automata didefinisikan dalam 5-tuple (Q, , , q0, F) di mana 1. Q adalah himpunan terbatas dari states, 2.  himpunan terbatas alphabet, 3. : Q ×   Q fungsi transisi, dinotasikan dengan (q,a)  p 4. q0  Q adalah start state, dan 5. F  Q adalah himpunan accept states (atau final states).


0

1

1

q1

0

q2

q3

Contoh : Deskripsi formal dari M1 dapat kita tulis sebagai 1. M1 = (Q, , , q1, F) 2. Q = {q1, q2, q3} 3.  = {0,1} 0 1 4.  dideskripsikan sebagai

5. q1 adalah start state 6. F = {q2}

q1

q1

q2

q2

q3

q2

q3

q2

q2

0,1


0 q1

1

1

0

q2

q3 0,1

Catatan : Dalam bahasa formal, aturan transisi () dapat pula dinotasikan dengan cara { (q1, 0)  q1; (q1, 1)  q2; (q2, 0)  q3; (q2, 1)  q2; (q3, 0)  q2; (q3, 1)  q2; }


Syarat sebuah STD dikatakan Deterministic Harus ada tepat 1 initial state. Minimal 1 final state. Dari setiap state, hanya ada satu busur yang meninggalkan state itu untuk setiap simbol dalam alphabet (menghindari ambigu).  untuk setiap simbol yang dibaca hanya ada 1 next state Harus Fully Defined  di setiap state harus mendefinisikan secara pasti setiap kemungkinan simbol dari alphabet yang muncul (menghindari no transition applicable).


Lihat kembali STD berikut!! Dari pertemuan sebelumnya, apakah mesin float kita ini termasuk deterministic FA???

Jika tidak, apa yang membuatnya tidak termasuk deterministic FA??


Mengubah STD menjadi Deterministic Berikut langkah-langkah mengubah suatu STD, yang belum deterministic dikarenakan belum fully defined, menjadi Deterministic FA 1. Tambahkan satu state baru, misalnya qx 2. Gambar busur dari qx ke dirinya sendiri (ke qx juga) dengan label semua simbol di alphabet. 3. Tambahkan busur dari states lainnya yang belum fully defined ke qx, dengan label simbol yang belum ada transisinya.


Contoh mengubah STD ke DFA [1] Kita tambahkan state baru q8 digit digit q1

q2 E

, q3

digit digit

q5 E +-

q4 q8

digit digit q7 q8

digit

q6

q8 digit E + - ,


Contoh mengubah STD ke DFA [2] Untuk setiap simbol di alphabet hubungkan busur dari dan ke q8 (dengan label semua simbol) digit digit q1

q2 E

, q3

digit digit

q5 E +-

q4 q8

digit digit q7 q8

digit

q6

q8 digit E + - ,


Contoh mengubah STD ke DFA [3] Tambahkan busur dari state lain yang belum fully defined ke state q8, sehingga menjadi fully defined digit q2

digit q1

E

, +-

q3

digit digit

q5 E +-

E+-, E+-,

q4 q8

digit digit

+-,

E,

q7 q8 E+-,

digit

q6

E+-,

q8 digit E + - ,


Latihan Lihat Buku 1 hal 36 no 2. Ubah STD berikut sehingga menjadi DFA yang ekivalen! Catatan:  = {a,b} b

q0

a

q1

b

q2

a

q3


Latihan Diketahui L = {100, 000, 001, 010} Buatkan DFA yang menerima bahasa L di atas! –STD yang hanya menerima string di dalam himpunan/bahasa L.


Language dari Mesin DFA [1] Kita akan menyebut himpunan string yang dapat diterima oleh suatu DFA sebagai suatu “language” dari DFA tersebut. Sebagai contoh, perhatikan STD berikut.

A adalah himpunan semua string yang diterima oleh mesin M. Oleh sebab itu, A adalah language dari mesin M (dinotasikan dengan L(M) = A). Teori Komputasi | CSG3D3

Language dari Mesin DFA [2] Secara harfiah, language dari Bahasa Indonesia adalah kalimat yang dapat disusun oleh grammer bahasa Indonesia. (jumlah kalimatnya tidak terbatas). Kembali lagi ke definisi bahwa language merupakan himpunan string yang dipilih dari Σ*, maka pada mesin M di gambar, language dari mesin tersebut adalah L(M) = {0, 00, 10, 000, 010, 100, 110, ..., 0000000, ...}


Tugas Latihan Soal 1 Yang menjadi pembeda antara Deterministic FA dan NonDeterministic FA adalah a. Ada/tidak transisi epsilon b. Fully Defined c. Ambigu / tidak dalam menentukan next state d. a, b, dan c benar e. b, dan c benar


Tugas Latihan Soal 2 Jika kita memiliki alphabet = {0, 1}, maka –Buatkan STD (DFA) yang menerima string biner dengan jumlah kemunculan angka 0 adalah genap. –Contoh string diterima : λ, 11, 110, 101, 110011, 10101010, dlsb.


Tugas Latihan Soal 3 Jika kita memiliki alphabet = {0, 1}, maka –Buatkan STD (DFA) yang menerima string biner dengan jumlah kemunculan angka 1 adalah genap. –Contoh string diterima : λ, 11, 110, 101, 110011, 10101010, dlsb.


Tugas Latihan Soal 4 Jika kita memiliki alphabet = {0, 1}, maka –Buatkan STD (DFA) yang menerima string biner dengan jumlah kemunculan angka 1 adalah genap dan sekaligus jumlah kemunculan angka 0-nya juga genap. –Contoh string diterima : λ, 11, 00, 1100, 1010, 0101, 0011, 111100, 101011, dlsb.


Tugas Latihan Soal 5 Jika kita memiliki alphabet = {a, b, c}, maka –Buatkan STD (DFA) yang menerima string dengan alphabet di atas dengan jumlah kemunculan simbol a adalah genap, b adalah genap, dan c adalah genap. –Contoh string diterima : λ, aa, bb, aabb, bbcc, aabbcc, aaaaaabbcc, abcaabbca, babacaca, dlsb.


Deterministic Finite Automata

Recommend Documents