Teori otomata: Perbedaan antara revisi
Tampilan
Konten dihapus Konten ditambahkan
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}} |