Diagram Transisi dan Tabel Transisi (Automata)

بِسْمِ اللّهِ الرَّحْمَنِ الرَّحِيْم

Assalamu’alaikum Wr. Wb

 

1. Finite Automata

• Suatu model komputer dengan jumlah memory yang sangat terbatas (Model komputasional yang paling sederhana)
• Digunakan pada aplikasi yang membutuhkan teknik pengenalan pola.
• Contoh : pada aplikasi kompilator, bagian leksikal harus bisa mengenali string mana yang merepresentasikan variable, nama, konstanta numerik, dan reserved word.

 

2. State Transition Diagram

• Transition diagram / state diagram : sekumpulan node berlabel terbatas, yang dihubungkan dengan garis yang disebut busur.
• Contoh di bawah ini adalah state transition diagram untuk mengenali variable (kita akan menyebutnya M1).
• State diagram akan menerima input string dan menghasilkan output berupa accept/reject

 

• M1 memiliki tiga states yakni: q0, q1, q2
• Start state / initial state q0 adalah state awal dari state transition diagram
• Accepted state / final state q2, dinotasikan dengan lingkaran ganda
• Transitions: panah yang memindahkan dari state satu ke state lainnya dengan menerima karakter input.
• Output dari mesin ini adalah accept (jika berhenti di Accepted State) or reject (selain itu)
• Contoh string input : X256, 789, 7uyt, variab apakah akan diterima?

 

Contoh String input X256 :

Pertama kali, state akan masuk ke q0 secara otomatis. Kemudian membaca alphabet “X” dan state berubah ke q2 membaca alphabet “2”, “5”, dan “6” berturut-turut state tetap di q2

 

Contoh Soal :

Buat diagram transisi untuk mengenali penulisan bilangan Real (mesin float).

Masukkan string berikut :

q 123459 (integer)

q 1234567,987 (real)

q 1234E (tidak valid)

q 1234E+ (tidak valid)

q 1234E56 (real)

q 1234E+56 (real)

q 1234E-56 (real)

 

Jawab :

4. Tabel Transisi

• Tabel transisi : tabel dua dimensi dimana nilai menggambarkan summary dari diagram transisi.
• Index pada baris adalah semua state dan index pada kolom meyatakan symbol yang mungkin muncul.
• Penambahan kolom ekstra dengan label EOS yang berisi accept or error.

tabel transisi dari M1

 

5. Cara Mengubah STD ke Tabel Transisi

1. Tambahkan sejumlah n baris state yang ada di STD (n menyatakan jumlah state)
2. Tambahkan sejumlah m kolom dari semua alfabet yang mungkin.
3. Tambahkan kolom EOS
4. Isi nilai di kolom EOS dengan “accept” untuk baris dimana accepted state berada
5. Isi dengan “error” untuk selainnya (di kolom EOS)
6. Untuk tiap-tiap baris, isikan nilai state berikutnya yang bersesuaian dengan alfabet.
7. sikan “error” untuk sel yang belum terisi.

 

Contoh Soal :

1. Ubah diagram transisi dari Mesin Float menjadi tabel transisi.

Jawab :

2. Buatkan State Transition Diagram, dan Tabel Transisi untuk kasus deteksi :

1. Bilangan ganjil pada string biner
2. Bilangan genap pada string biner
3. Kemunculan substring 111 pada string biner
4. Kemunculan substring 0101 pada string biner
5. Bagian leksik yang mengenali kemunculan string “:=“, sekaligus Angka, sekaligus variabel.

 

Jawab :

1. Mesin Ganjil

• Mesin terdiri dari dua state : q0 dan q1.
• Charakter input : 0, 1
• Lihat bahwa accepted state selalu menerima charakter 1.
• Contoh String yang dikenali mesin 100001, 1111111, 0000001, dan sebagainya

 

2. Mesin Genap

• Contoh string yang diterima mesin ini adalah 0, 00, 10, 1111110, 000000010, dan sebagainya

 

3.  Mesin 111

• Contoh string yang diterima mesin ini adalah 111, 1111110, 000001110, dan sebagainya
  

 

4. Mesin 0101

• Contoh string yang diterima mesin ini adalah 0101, 000101, 000001010, 1111110101111 dan sebagainya

 

5. Mesin Variabel, Angka dan Assignment