Teori otomata
Teori Otomata adalah teori mengenai mesin-mesin abstrak, dan berkaitan erat dengan teori bahasa formal.
Otomata Berhingga
Definisi Formal
Otomata adalah sebuah 5-tupel :
- adalah himpunan berhingga dari state,
- adalah himpunan simbol-simbol,
- adalah fungsi transisi
- adalah simbol awal
- adalah state akhir
Jenis-jenis Otomata Berhingga
Otomata Berhingga Deterministik
Otomata berhingga deterministik (DFA - Deterministic Finite Automata) adalah sebuah otomata yang fungsi transisinya adalah:
Otomata Berhingga Non-Deterministik
Otomata berhingga non-deterministik (NFA - Nondeterministic Finite Automata) berbeda dengan DFA dalam hal fungsi transisinya:
Fungsi transisi dalam NFA memetakan pasangan dan 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 , di mana:
- adalah himpunan berhingga dari state,
- adalah himpunan simbol-simbol,
- adalah simbol awal
- adalah state akhir
Ditambah dengan dua unsur, untuk menangani stack:
- adalah himpunan berhingga simbol-simbol stack,
- adalah simbol awal stack,
Dengan fungsi transisinya adalah
- adalah fungsi transisi
Otomata Terbatas Linear
Mesin Turing
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