Lihat sumber Teori otomata

'''Teori otomata''' adalah teori mengenai mesin-mesin abstrak, dan berkaitan erat dengan teori [[bahasa formal]].
Ada beberapa hal yang berkaitan dengan Otomata, yaitu [[tata bahasa]].
Dalam maksud ini, tata bahasa adalah bentuk abstrak yang dapat diterima untuk membangkitkan suatu kalimat otomata berdasarkan aturan tertentu.

== Konsep dasar ==
*Anggota alfabet dinamakan simbol terminal
*Kalimat adalah deretan sampai simbol-simbol terminal.
*Bahasa adalah himpunan kalimat-kalimat.
*Simbol-simbol berikut adalah simbol terminal:
** Huruf kecil, misalnya: a, b, c
** Simbol operator, misalnya: +, , dan *
** [[tanda baca]], misalnya: (, ), dan ;
* Rangkaian (string) yang tercetak tebal, misalnya: '''if''', '''then''', dan '''else'''.

=== Non-terminal ===
* Simbol-simbol berikut adalah simbol non terminal/variabel:
** Huruf besar, misalnya: A, B, C
** Huruf S sebagai simbol awal
** Rangakaian yang tercetak miring, misalnya ''expr''.

=== Konsep lain ===
* Huruf yunani melambangkan rangkaian yang tersusun dari simbol-simbol terminal atau yang non-terminal atau campuran keduanya, misalnya α,β, dan ε.
* Penurunan (derivasi) adalah proses pembentukan sebuah kalimat (sentensial).
* Sebuah produksi dilambangkan sebagai α --> β, artinya: dalam sebuah penurunan dapat dilakukan penggantian simbol α dengan simbol β.
* Kalimat adalah rangkaian yang tersusun atas simbol-simbol terminal atau yang non terminal atau campuran keduanya.
* Kalimat adalah string yang tersusun atas simbol-simbol terminal. Kalimat merupakan sentensial, sebaliknya belum tentu.

== Tata bahasa ==
Tata bahasa G diartikan sebagai pasangan 4 tupel: 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), di mana:
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 --> [[American Broadcasting Company|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,…}

== Pengertian 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 peralihan
* <math>q_0 \in Q</math> adalah simbol awal
* <math>F \subset Q</math> adalah keadaan akhir

== Jenis ==

=== Otomata Berhingga Bertentu ===
Otomata berhingga bertentu ('''DFA''' - ''Deterministic Finite Automata'') adalah sebuah otomata yang fungsi peralihannya adalah:
:<math>\delta: Q \times \Sigma \rightarrow Q</math>
:Contoh
:Konfigurasi DFA disamping secara formal dinyatakan sebagai berikut Q = {q0, q1, q2, q3 } Σ = {0,1} S = q0 F = { q0} <br />Fungsi peralihan (transition), biasanya fungsi-fungsi ini kita sajikan dalam sebuah tabel peralihan. Tabel peralihan tersebut menunjukkan keadaan-keadaan berikutnya untuk paduan dan masukan tertentu.

=== Otomata Berhingga Takbertentu ===
Otomata berhingga takbertentu ('''NFA''' - ''Nondeterministic Finite Automata'') berbeda dengan DFA dalam fungsi peralihannya:
:<math>\delta: Q \times \Sigma \rightarrow \mathcal{P}(Q)</math>
:

Fungsi peralihan dalam NFA memetakan pasangan <math>Q</math> dan <math>\Sigma</math> kepada [[himpunan kuasa]] dari Q. Fungsi peralihan yang diartikan seperti ini memungkinkan suatu simbol masukan menyebabkan peralihan dari sebuah keadaan (state) ke beberapa kemungkinan keadaan lainnya.

Contoh NFA:


* Rangkaian diterima NFA bila terdapat suatu urutan peralihan berdasarkan masukan, dari keadaan awal sampai akhir.
* Semua kemungkinan harus dicoba.


=== Otomata Dorong ke Bawah ===
Otomata dorong ke bawah ('''otomata pushdown''') adalah salah satu ragam 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 keadaan,
* <math>\Sigma</math> adalah himpunan simbol-simbol,
* <math>q_0 \in Q</math> adalah simbol awal
* <math>F \subset Q</math> adalah keadaan akhir
Ditambah dengan dua unsur, untuk menangani tumpukan:
* <math>\Gamma</math> adalah himpunan berhingga simbol-simbol tumpukan,
* <math>Z_0 \in \Gamma</math> adalah simbol awal tumpukan,
Dengan fungsi peralihannya adalah
:<math>\delta: Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma) \rightarrow Q \times \Gamma^*</math> adalah fungsi peralihan

== Hubungan dengan tata bahasa ==
Setiap otomata berhingga dapat digunakan untuk mengenali bahasa tertentu.

== Referensi ==


== Pranala luar ==
* [https://web.archive.org/web/20090503173000/http://www.cs.usfca.edu/~jbovet/vas.html Visual Automata Simulator], a tool for simulating, visualizing and transforming finite-state automata and Turing Machines, by Jean Bovet
* [http://www.jflap.org JFLAP]
* [http://www.brics.dk/automaton dk.brics.automaton]
* [http://www.augeas.net/libfa/index.html libfa]



== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Teori+otomata&oldid=28895850 Wikipedia bahasa Indonesia], revisi 28895850 (2026-01-26T23:25:55Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.