Teori otomata

Teori otomata adalah teori mengenai mesin-mesin abstrak, dan berkaitan erat dengan teori bahasa formal.
Ada beberapa hal yang berkaitan dengan Otomata, yaitu tata bahasa.
Dalam maksud ini, tata bahasa adalah bentuk abstrak yang dapat diterima untuk membangkitkan suatu kalimat otomata berdasarkan aturan tertentu.

 Konsep dasar 
Anggota alfabet dinamakan simbol terminal
Kalimat adalah deretan sampai simbol-simbol terminal.
Bahasa adalah himpunan kalimat-kalimat.
Simbol-simbol berikut adalah simbol terminal:
 Huruf kecil, misalnya: a, b, c
 Simbol operator, misalnya: +, , dan *
 tanda baca, misalnya: (, ), dan ;
 Rangkaian (string) yang tercetak tebal, misalnya: if, then, dan else.

 Non-terminal 
 Simbol-simbol berikut adalah simbol non terminal/variabel:
 Huruf besar, misalnya: A, B, C
 Huruf S sebagai simbol awal
 Rangakaian yang tercetak miring, misalnya expr.

 Konsep lain 
 Huruf yunani melambangkan rangkaian yang tersusun dari simbol-simbol terminal atau yang non-terminal atau campuran keduanya, misalnya α,β, dan ε.
 Penurunan (derivasi) adalah proses pembentukan sebuah kalimat (sentensial).
 Sebuah produksi dilambangkan sebagai α --> β, artinya: dalam sebuah penurunan dapat dilakukan penggantian simbol α dengan simbol β.
 Kalimat adalah rangkaian yang tersusun atas simbol-simbol terminal atau yang non terminal atau campuran keduanya.
 Kalimat adalah string yang tersusun atas simbol-simbol terminal. Kalimat merupakan sentensial, sebaliknya belum tentu.

 Tata bahasa 
Tata bahasa G diartikan sebagai pasangan 4 tupel: Vt, Vn, S, dan P, dan dituliskan sebagai G(Vt, Vn, S, P), di mana:
Vt 	: himpunan simbol-simbol terminal (alfabet) = kamus
Vn 	: himpunan simbol-simbol non terminal
S C V 	: simbol awal (atau simbol start)
P	: himpunan produksi

Contoh:

1. G1: VT = {I, want, need, You}, V = {S,A,B,C},
			P = {S --> ABC, A--> I, B--> want | need, C--> You}

S --> ABC
   --> IwantYou

L(G1)={IwantYou,IneedYou}

2. . G2: VT = {a}, V = {S}, P = {S  aS | a}

S --> aS
  --> aaS
  --> aaa                    L(G2) ={an --> n ≥ 1}

             L(G2)={a, aa, aaa, aaaa,…}

 Pengertian formal 
Otomata adalah sebuah 5-tupel :
  adalah himpunan berhingga dari state,
  adalah himpunan simbol-simbol,
  adalah fungsi peralihan
  adalah simbol awal
  adalah keadaan akhir

 Jenis 

 Otomata Berhingga Bertentu 
Otomata berhingga bertentu (DFA - Deterministic Finite Automata) adalah sebuah otomata yang fungsi peralihannya adalah:

Contoh
jmpl|Mesin dfaKonfigurasi DFA disamping secara formal dinyatakan sebagai berikut Q = {q0, q1, q2, q3 } Σ = {0,1} S = q0 F = { q0} Fungsi peralihan (transition), biasanya fungsi-fungsi ini kita sajikan dalam sebuah tabel peralihan. Tabel peralihan tersebut menunjukkan keadaan-keadaan berikutnya untuk paduan dan masukan tertentu.

 Otomata Berhingga Takbertentu 
Otomata berhingga takbertentu (NFA - Nondeterministic Finite Automata) berbeda dengan DFA dalam fungsi peralihannya:

Fungsi peralihan dalam NFA memetakan pasangan  dan  kepada himpunan kuasa dari Q. Fungsi peralihan yang diartikan seperti ini memungkinkan suatu simbol masukan menyebabkan peralihan dari sebuah keadaan (state) ke beberapa kemungkinan keadaan lainnya.

Contoh NFA:
jmpl|string 01001

 Rangkaian diterima NFA bila terdapat suatu urutan peralihan berdasarkan masukan, dari keadaan awal sampai akhir.
 Semua kemungkinan harus dicoba.

 Otomata Dorong ke Bawah 
Otomata dorong ke bawah (otomata pushdown) adalah salah satu ragam otomata dengan 7-tupel , di mana:
  adalah himpunan berhingga dari keadaan,
  adalah himpunan simbol-simbol,
  adalah simbol awal
  adalah keadaan akhir
Ditambah dengan dua unsur, untuk menangani tumpukan:
  adalah himpunan berhingga simbol-simbol tumpukan,
  adalah simbol awal tumpukan,
Dengan fungsi peralihannya adalah
 adalah fungsi peralihan

 Hubungan dengan tata bahasa 
Setiap otomata berhingga dapat digunakan untuk mengenali bahasa tertentu.

 Referensi 

 Pranala luar 
 Visual Automata Simulator, a tool for simulating, visualizing and transforming finite-state automata and Turing Machines, by Jean Bovet
 JFLAP
 dk.brics.automaton
 libfa

Kategori:Komputasi
Kategori:Matematika diskrit