Teori otomata: Perbedaan antara revisi
Tampilan
Konten dihapus Konten ditambahkan
(10 revisi perantara oleh 6 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: |
||
⚫ | |||
⚫ | |||
⚫ | |||
* simbol tanda baca, misalnya : (, ), dan ;<ref>double</ref> |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
* |
* simbol tanda baca, misalnya: (, ), dan ; |
||
⚫ | |||
⚫ | |||
⚫ | |||
* huruf besar, misalnya: A, B, C |
|||
* huruf S sebagai simbol awal |
* huruf S sebagai simbol awal |
||
* string yang tercetak miring, misalnya |
* 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 |
• 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 |
• 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 |
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 |
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 |
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 |
||
== 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 |
[[Kategori:Matematika diskrit]] |