Teori otomata

Teori Otomata adalah teori mengenai mesin-mesin abstrak, dan berkaitan erat dengan teori bahasa formal.

Definisi 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 transisi
• $q_{0}\in Q$ adalah simbol awal
• $F\subset Q$ adalah state akhir

Jenis-jenis Otomata Berhingga

Otomata Berhingga Deterministik

Otomata berhingga deterministik (DFA - Deterministic Finite Automata) adalah sebuah otomata yang fungsi transisinya adalah:

$\delta :Q\times \Sigma \rightarrow Q$

Otomata Berhingga Non-Deterministik

Otomata berhingga non-deterministik (NFA - Nondeterministic Finite Automata) berbeda dengan DFA dalam hal fungsi transisinya:

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

Fungsi transisi dalam NFA memetakan pasangan $Q$ dan $\Sigma$ kepada himpunan kuasa dari Q. Fungsi transisi yang didefinisikan seperti ini memungkinkan suatu simbol masukan untuk mengakibatkan transisi dari sebuah state ke beberapa kemungkinan state yang lain.

Otomata Pushdown

Otomata Pushdown adalah salah satu varian otomata dengan 7-tupel $\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},Z_{0},F\rangle$, di mana:

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

Ditambah dengan dua unsur, untuk menangani stack:

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

Dengan fungsi transisinya adalah

$\delta :Q\times (\Sigma \cup \{\epsilon \})\times \Gamma )\rightarrow Q\times \Gamma ^{*}$ adalah fungsi transisi

Hubungan dengan Tata Bahasa

Setiap otomata berhingga dapat digunakan untuk mengenali bahasa tertentu.

Referensi

• John E. Hopcroft, Jeffrey D. Ullman - Introduction to Automata Theory, Languages, and Computation