Lompat ke isi

Teori otomata: Perbedaan antara revisi

Tambah pranala
Jelajahi riwayat secara interaktif
← Revisi sebelumnya
Konten dihapus Konten ditambahkan
VisualTeks wiki
HsfBot (bicara | kontrib)
Bot
1.172.010 suntingan
k Bot: Perubahan kosmetika
 
(11 revisi perantara oleh 7 pengguna tidak ditampilkan)
Baris 12: Baris 12:
• Bahasa adalah himpunan kalimat-kalimat. Anggota bahasa bisa tak hingga kalimat.
• Bahasa adalah himpunan kalimat-kalimat. Anggota bahasa bisa tak hingga kalimat.


• Simbol-simbol berikut adalah simbol terminal :
• 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'''.


⚫
* huruf kecil, misalnya: a, b, c
⚫
* simbol operator, misalnya: +, , dan *
⚫
• Simbol-simbol berikut adalah simbol non terminal /Variabel :
* huruf besar, misalnya : A, B, C
* 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
* huruf S sebagai simbol awal
* string yang tercetak miring, misalnya : ''expr''
* 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 ε
• 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 β.
• 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 : α ==> β.
• 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.
• 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..
• Kalimat adalah string yang tersusun atas simbol-simbol terminal. Kalimat adalah merupakan sentensial, sebaliknya belum tentu..
Grammar :
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 :
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>t</sub> : himpunan simbol-simbol terminal (alfabet) = kamus
Baris 44: Baris 44:
P : himpunan produksi
P : himpunan produksi


Contoh :
Contoh:


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


Baris 54: Baris 54:
L(G1)={IwantYou,IneedYou}
L(G1)={IwantYou,IneedYou}


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


S --> aS
S --> aS
Baris 75: Baris 75:
Otomata berhingga deterministik ('''DFA''' - ''Deterministic Finite Automata'') adalah sebuah otomata yang fungsi transisinya adalah:
Otomata berhingga deterministik ('''DFA''' - ''Deterministic Finite Automata'') adalah sebuah otomata yang fungsi transisinya adalah:
:<math>\delta: Q \times \Sigma \rightarrow Q</math>
:<math>\delta: Q \times \Sigma \rightarrow Q</math>
:Contoh
:[[Berkas:DFA_Machine_Learn.jpg|jmpl|Mesin dfa]]Konfigurasi DFA disamping secara formal dinyatakan sebagai berikut Q = {q0, q1, q2, q3 } Σ = {0,1} S = q0 F = { q0} <br />Fungsi transisi, biasanya fungsi-fungsi transisi ini kita sajikan dalam sebuah tabel transisi. Tabel transisi tersebut menunjukkan state state berikutnya untuk kombinasi state state dan input. Tabel transisi dari fungsi transisi adalah


=== Otomata Berhingga Non-Deterministik ===
=== Otomata Berhingga Non-Deterministik ===
Otomata berhingga non-deterministik ('''NFA''' - ''Nondeterministic Finite Automata'') berbeda dengan DFA dalam hal fungsi transisinya:
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>
:<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.
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.

Contoh NFA:
[[Berkas:NFA.jpg|jmpl|string 01001]]

* String diterima NFA bila terdapat suatu urutan transisi berdasarkan input, dari state awal ke state akhir.
* harus mencoba semua kemungkinan.



=== Otomata Pushdown ===
=== Otomata Pushdown ===
Baris 93: Baris 104:
:<math>\delta: Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma) \rightarrow Q \times \Gamma^*</math> adalah fungsi transisi
:<math>\delta: Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma) \rightarrow Q \times \Gamma^*</math> adalah fungsi transisi


=== Otomata Terbatas Linear ===
== Hubungan dengan tata bahasa ==

=== Mesin Turing ===

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


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


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

{{Authority control}}
{{matematika-stub}}
{{matematika-stub}}


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

[[en:Automata Theory]]
Diperoleh dari "https://wiki-indonesia.club/wiki/Teori_otomata"