Otomata & Teori Bahasa Formal (automata and formal language theory)

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

Jenis-jenis Otomata

Otomata Berhingga Deterministik

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

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

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

Fungsi transisi dalam NFA memetakan pasangan ${\displaystyle Q}$ dan ${\displaystyle \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 ${\displaystyle \langle Q,\Sigma ,\Gamma ,\delta ,q_{0},Z_{0},F\rangle }$, di mana:

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

Ditambah dengan dua unsur, untuk menangani stack:

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

Dengan fungsi transisinya adalah

adalah fungsi transisi 

Semoga Bermanfaat !!!

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