Teori otomata: Perbedaan antara revisi

'''Teori Otomata''' adalah teori mengenai mesin-mesin abstrak, dan berkaitan erat dengan teori [[bahasa formal]].

 

 

Otomata adalah sebuah 5-tupel <math>\langle Q, \Sigma, \delta, q_0, F\rangle</math>:

* <math>Q</math> adalah himpunan berhingga dari ''state'',

* <math>F \subset Q</math> adalah ''state'' akhir

 

 

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 ('''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''' 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>\delta: Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma) \rightarrow Q \times \Gamma^*</math> adalah fungsi transisi

 

 

 

Setiap otomata berhingga dapat digunakan untuk mengenali bahasa tertentu.

 

* [[John E. Hopcroft]], [[Jeffrey D. Ullman]] - ''Introduction to Automata Theory, Languages, and Computation''