Lihat sumber Teori otomata

{{rapikan|topik=teknologi informasi}}
'''Teori Otomata''' adalah teori mengenai mesin-mesin abstrak, dan berkaitan erat dengan teori [[bahasa formal]].
ada beberapa hal yang berkaitan dengan Otomata, yaitu Grammar.
Grammar adalah bentuk abstrak yang dapat diterima (accept) untuk membangkitkan suatu kalimat otomata berdasarkan suatu aturan tertentu.

== Konsep Dasar ==

•	Anggota alfabet dinamakan simbol terminal.

•	Kalimat adalah deretan hingga simbol-simbol terminal.

•	Bahasa adalah himpunan kalimat-kalimat. Anggota bahasa bisa tak hingga kalimat.

•	Simbol-simbol berikut adalah simbol terminal :
	
* huruf kecil, misalnya : a, b, c
* simbol operator, misalnya : +, , dan *
* simbol tanda baca, misalnya : (, ), dan ;
* simbol tanda baca, misalnya : (, ), dan ;<ref>double</ref>
* string yang tercetak tebal, misalnya : '''if''', '''then''', dan '''else'''.

	
•	Simbol-simbol berikut adalah simbol non terminal /Variabel :
*	huruf besar, misalnya : A, B, C
*	huruf S sebagai simbol awal
*	string yang tercetak miring, misalnya : ''expr''

•	Huruf yunani melambangkan string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya, misalnya : α,β, dan ε

•	Sebuah produksi dilambangkan sebagai α --> β, artinya : dalam sebuah derivasi dapat dilakukan penggantian simbol α dengan simbol β.

•	Derivasi adalah proses pembentukan sebuah kalimat atau sentensial. Sebuah derivasi dilambangkan sebagai : α ==> β.

•	Sentensial adalah string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya.

•	Kalimat adalah string yang tersusun atas simbol-simbol terminal. Kalimat adalah merupakan sentensial, sebaliknya belum tentu..
Grammar :

Grammar G didefinisikan sebagai pasangan 4 tuple : V<sub>t</sub> , V<sub>n</sub> , S, dan P, dan dituliskan sebagai G(V<sub>t</sub> , V<sub>n</sub> , S, P), dimana :

V<sub>t</sub> 	: himpunan simbol-simbol terminal (alfabet) = kamus
V<sub>n</sub> 	: himpunan simbol-simbol non terminal
S <s>C</s> V 	: simbol awal (atau simbol start)
P	: himpunan produksi

Contoh :

1. G1 : VT = {I, want, need, You}, V = {S,A,B,C},
			P = {S --> ABC, A--> I, B--> want | need, C--> You}

S --> ABC
   --> IwantYou

L(G1)={IwantYou,IneedYou}

2. . G2 : VT = {a}, V = {S}, P = {S  aS | a}

S --> aS
  --> aaS
  --> aaa                    L(G2) ={an --> n ≥ 1}

             L(G2)={a, aa, aaa, aaaa,…}

== Definisi 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>\Sigma</math> adalah himpunan simbol-simbol,
* <math>\delta</math> adalah fungsi transisi
* <math>q_0 \in Q</math> adalah simbol awal
* <math>F \subset Q</math> adalah ''state'' akhir

== Jenis-jenis Otomata ==

=== 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 ==
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}}

[[Kategori:Komputasi]]
[[Kategori:Matematika Diskrit]]