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: V_t, V_n, S, dan P, dan dituliskan sebagai G(V_t, V_n, S, P), di mana: V_t : himpunan simbol-simbol terminal (alfabet) = kamus V_n : 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 ${\displaystyle \langle Q,\Sigma ,\delta ,q_{0},F\rangle }$:

• ${\displaystyle Q}$ adalah himpunan berhingga dari state,
• ${\displaystyle \Sigma }$ adalah himpunan simbol-simbol,
• ${\displaystyle \delta }$ adalah fungsi peralihan
• ${\displaystyle q_{0}\in Q}$ adalah simbol awal
• ${\displaystyle F\subset Q}$ adalah keadaan akhir

Jenis

Otomata Berhingga Bertentu

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

${\displaystyle \delta :Q\times \Sigma \rightarrow Q}$

Contoh

Mesin dfa

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:

${\displaystyle \delta :Q\times \Sigma \rightarrow {\mathcal {P}}(Q)}$

Fungsi peralihan dalam NFA memetakan pasangan ${\displaystyle Q}$ dan ${\displaystyle \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:

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 ${\displaystyle \langle Q,\Sigma ,\Gamma ,\delta ,q_{0},Z_{0},F\rangle }$, di mana:

• ${\displaystyle Q}$ adalah himpunan berhingga dari keadaan,
• ${\displaystyle \Sigma }$ adalah himpunan simbol-simbol,
• ${\displaystyle q_{0}\in Q}$ adalah simbol awal
• ${\displaystyle F\subset Q}$ adalah keadaan akhir

Ditambah dengan dua unsur, untuk menangani tumpukan:

• ${\displaystyle \Gamma }$ adalah himpunan berhingga simbol-simbol tumpukan,
• ${\displaystyle Z_{0}\in \Gamma }$ adalah simbol awal tumpukan,

Dengan fungsi peralihannya adalah

${\displaystyle \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.