Teori otomata: Perbedaan antara revisi
k Suntingan 219.83.2.47 (Pembicaraan) dikembalikan ke versi terakhir oleh RPras |
k Robot: Cosmetic changes |
||
Baris 1: | Baris 1: | ||
'''Teori Otomata''' adalah teori mengenai mesin-mesin abstrak, dan berkaitan erat dengan teori [[bahasa formal]]. |
'''Teori Otomata''' adalah teori mengenai mesin-mesin abstrak, dan berkaitan erat dengan teori [[bahasa formal]]. |
||
==Otomata Berhingga== |
== Otomata Berhingga == |
||
==Definisi Formal== |
== Definisi Formal == |
||
Otomata adalah sebuah 5-tupel <math>\langle Q, \Sigma, \delta, q_0, F\rangle</math>: |
Otomata adalah sebuah 5-tupel <math>\langle Q, \Sigma, \delta, q_0, F\rangle</math>: |
||
* <math>Q</math> adalah himpunan berhingga dari ''state'', |
* <math>Q</math> adalah himpunan berhingga dari ''state'', |
||
Baris 11: | Baris 11: | ||
* <math>F \subset Q</math> adalah ''state'' akhir |
* <math>F \subset Q</math> adalah ''state'' akhir |
||
==Jenis-jenis Otomata Berhingga== |
== Jenis-jenis Otomata Berhingga == |
||
===Otomata Berhingga Deterministik=== |
=== Otomata Berhingga Deterministik === |
||
Otomata berhingga deterministik ('''DFA''' - ''Deterministic Finite Automata'') adalah sebuah otomata yang fungsi transisinya adalah: |
Otomata berhingga deterministik ('''DFA''' - ''Deterministic Finite Automata'') adalah sebuah otomata yang fungsi transisinya adalah: |
||
:<math>\delta: Q \times \Sigma \rightarrow Q</math> |
:<math>\delta: Q \times \Sigma \rightarrow Q</math> |
||
===Otomata Berhingga Non-Deterministik=== |
=== Otomata Berhingga Non-Deterministik === |
||
Otomata berhingga non-deterministik ('''NFA''' - ''Nondeterministic Finite Automata'') berbeda dengan DFA dalam hal fungsi transisinya: |
Otomata berhingga non-deterministik ('''NFA''' - ''Nondeterministic Finite Automata'') berbeda dengan DFA dalam hal fungsi transisinya: |
||
:<math>\delta: Q \times \Sigma \rightarrow \mathcal{P}(Q)</math> |
:<math>\delta: Q \times \Sigma \rightarrow \mathcal{P}(Q)</math> |
||
Fungsi transisi dalam NFA memetakan pasangan <math>Q</math> dan <math>\Sigma</math> 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. |
Fungsi transisi dalam NFA memetakan pasangan <math>Q</math> dan <math>\Sigma</math> 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 === |
||
'''Otomata Pushdown''' adalah salah satu varian otomata dengan 7-tupel <math>\langle Q, \Sigma, \Gamma, \delta, q_0, Z_0, F\rangle</math>, di mana: |
'''Otomata Pushdown''' adalah salah satu varian otomata dengan 7-tupel <math>\langle Q, \Sigma, \Gamma, \delta, q_0, Z_0, F\rangle</math>, di mana: |
||
* <math>Q</math> adalah himpunan berhingga dari ''state'', |
* <math>Q</math> adalah himpunan berhingga dari ''state'', |
||
Baris 34: | Baris 34: | ||
:<math>\delta: Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma) \rightarrow Q \times \Gamma^*</math> adalah fungsi transisi |
:<math>\delta: Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma) \rightarrow Q \times \Gamma^*</math> adalah fungsi transisi |
||
===Otomata Terbatas Linear=== |
=== Otomata Terbatas Linear === |
||
===Mesin Turing=== |
=== Mesin Turing === |
||
==Hubungan dengan Tata Bahasa== |
== Hubungan dengan Tata Bahasa == |
||
Setiap otomata berhingga dapat digunakan untuk mengenali bahasa tertentu. |
Setiap otomata berhingga dapat digunakan untuk mengenali bahasa tertentu. |
||
==Referensi== |
== Referensi == |
||
* [[John E. Hopcroft]], [[Jeffrey D. Ullman]] - ''Introduction to Automata Theory, Languages, and Computation'' |
* [[John E. Hopcroft]], [[Jeffrey D. Ullman]] - ''Introduction to Automata Theory, Languages, and Computation'' |
||
Revisi per 11 Maret 2008 04.40
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