Teori otomata

Artikel ini perlu dirapikan agar memenuhi standar Wikipedia. Silakan kembangkan artikel ini semampu Anda. Merapikan artikel dapat dilakukan dengan wikifikasi atau membagi artikel ke paragraf-paragraf. Jika sudah dirapikan, silakan hapus templat ini. (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini)

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.

• 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.

• 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.

• 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 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,…}

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

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

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

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

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

Setiap otomata berhingga dapat digunakan untuk mengenali bahasa tertentu.

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

Artikel bertopik matematika ini adalah sebuah rintisan. Anda dapat membantu Wikipedia dengan mengembangkannya.

• l
• b
• s