Teori otomata: Perbedaan antara revisi
Tidak ada ringkasan suntingan |
|||
Baris 1: | Baris 1: | ||
{{kembangkan|25 Mei 2007}} |
{{kembangkan|25 Mei 2007}} |
||
''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 |
==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 13: | Baris 13: | ||
==Jenis-jenis Otomata Berhingga== |
==Jenis-jenis Otomata Berhingga== |
||
===Otomata Berhingga Deterministik=== |
|||
Otomata berhingga deterministik ('''DFA''' - ''Deterministic Finite Automata'') adalah sebuah otomata yang fungsi transisinya adalah: |
|||
:<math>\delta: Q \times \Sigma \rightarrow Q</math> |
|||
===Otomata Berhingga Non-Deterministik=== |
|||
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> |
|||
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''' 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>\Sigma</math> adalah himpunan simbol-simbol, |
|||
* <math>q_0 \in Q</math> adalah simbol awal |
|||
* <math>F \subset Q</math> adalah ''state'' akhir |
|||
Ditambah dengan dua unsur, untuk menangani ''stack'': |
|||
* <math>\Gamma</math> adalah himpunan berhingga simbol-simbol ''stack'', |
|||
* <math>Z_0 \in \Gamma</math> adalah simbol awal ''stack'', |
|||
Dengan fungsi transisinya adalah |
|||
:<math>\delta: Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma) \rightarrow Q \times \Gamma^*</math> adalah fungsi transisi |
|||
===Otomata Terbatas Linear=== |
|||
===Mesin Turing=== |
|||
==Hubungan dengan Tata Bahasa== |
==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'' |
|||
{{matematika-stub}} |
{{matematika-stub}} |
Revisi per 14 Mei 2007 06.56
Artikel ini perlu dikembangkan agar dapat memenuhi kriteria sebagai entri Wikipedia. Bantulah untuk mengembangkan artikel ini. Jika tidak dikembangkan, artikel ini akan dihapus pada 25 Mei 2007. |
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