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 \langle Q, \Sigma, \delta, q_0, F\rangle:
* Q adalah himpunan berhingga dari *state*,
* \Sigma adalah himpunan simbol-simbol,
* \delta adalah fungsi peralihan
* q_0 \in Q adalah simbol awal
* F \subset Q adalah keadaan akhir

## Jenis

### Otomata Berhingga Bertentu
Otomata berhingga bertentu (**DFA** - *Deterministic Finite Automata*) adalah sebuah otomata yang fungsi peralihannya adalah:
:\delta: Q \times \Sigma \rightarrow Q
:Contoh
:Konfigurasi 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:
:\delta: Q \times \Sigma \rightarrow \mathcal{P}(Q)
:

Fungsi peralihan dalam NFA memetakan pasangan Q dan \Sigma 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:

* 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 \langle Q, \Sigma, \Gamma, \delta, q_0, Z_0, F\rangle, di mana:
* Q adalah himpunan berhingga dari keadaan,
* \Sigma adalah himpunan simbol-simbol,
* q_0 \in Q adalah simbol awal
* F \subset Q adalah keadaan akhir
Ditambah dengan dua unsur, untuk menangani tumpukan:
* \Gamma adalah himpunan berhingga simbol-simbol tumpukan,
* Z_0 \in \Gamma adalah simbol awal tumpukan,
Dengan fungsi peralihannya adalah
:\delta: Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma) \rightarrow Q \times \Gamma^* 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