Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

2026-08-23T04:07:19Z

Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

← Revisi sebelumnya		Revisi per 23 Agustus 2026 04.07
Baris 60:		Baris 60:

	== Jenis ==		== Jenis ==

	=== Otomata Berhingga Bertentu ===		=== Otomata Berhingga Bertentu ===
	Otomata berhingga bertentu ('''DFA''' - ''Deterministic Finite Automata'') adalah sebuah otomata yang fungsi peralihannya adalah:		Otomata berhingga bertentu ('''DFA''' - ''Deterministic Finite Automata'') adalah sebuah otomata yang fungsi peralihannya adalah:
Baris 75:		Baris 74:

	Contoh NFA:		Contoh NFA:


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


	=== Otomata Dorong ke Bawah ===		=== Otomata Dorong ke Bawah ===
Baris 95:		Baris 92:
	== Hubungan dengan tata bahasa ==		== Hubungan dengan tata bahasa ==
	Setiap otomata berhingga dapat digunakan untuk mengenali bahasa tertentu.		Setiap otomata berhingga dapat digunakan untuk mengenali bahasa tertentu.

	~~== Referensi ==~~


	== Pranala luar ==		== Pranala luar ==
Baris 104:		Baris 98:
	* [http://www.brics.dk/automaton dk.brics.automaton]		* [http://www.brics.dk/automaton dk.brics.automaton]
	* [http://www.augeas.net/libfa/index.html libfa]		* [http://www.augeas.net/libfa/index.html libfa]



	== Sumber dan atribusi ==		== 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.		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.

			<!-- WIKI_UNISSULA_PRESENTATION_V4 -->

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 28895850; atribusi sumber disertakan.

2026-08-23T03:30:04Z

Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 28895850; atribusi sumber disertakan.

Halaman baru

'''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: Vt, Vn, S, dan P, dan dituliskan sebagai G(Vt, Vn, S, P), di mana:
Vt : himpunan simbol-simbol terminal (alfabet) = kamus
Vn : 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} 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.

Teori otomata - Riwayat revisi

Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 28895850; atribusi sumber disertakan.