Teori otomata: Perbedaan antara revisi

Jelajahi riwayat secara interaktif

← Revisi sebelumnya

Konten dihapus Konten ditambahkan

VisualTeks wiki

Revisi per 27 Januari 2017 15.26 sunting HsfBot (bicara \| kontrib) Bot 1.172.010 suntingan k Bot: Perubahan kosmetika ← Revisi sebelumnya		Revisi terkini sejak 18 Januari 2022 08.02 sunting balikkan 36.72.217.128 (bicara) →‎Hubungan dengan Tata Bahasa
(11 revisi perantara oleh 7 pengguna tidak ditampilkan)
Baris 12: • 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'''.▼ ▲* huruf kecil, misalnya : a, b, c ▲* simbol operator, misalnya : +, , dan * • Simbol-simbol berikut adalah simbol non terminal /Variabel :▼ * ~~huruf~~ ~~besar~~simbol tanda baca, misalnya : A(, B), Cdan ; ▲* 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 Baris 44: 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} Baris 54: L(G1)={IwantYou,IneedYou} 2. . G2 : VT = {a}, V = {S}, P = {S  aS \| a} S --> aS Baris 75: Otomata berhingga deterministik ('''DFA''' - ''Deterministic Finite Automata'') adalah sebuah otomata yang fungsi transisinya adalah: :<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 ('''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. 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 === Baris 93 ⟶ 104: :<math>\delta: Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma) \rightarrow Q \times \Gamma^</math> adalah fungsi transisi === ~~Otomata~~Hubungan ~~Terbatas~~dengan ~~Linear~~tata bahasa === ~~=== Mesin Turing ===~~ ~~== Hubungan dengan Tata Bahasa ==~~ Setiap otomata berhingga dapat digunakan untuk mengenali bahasa tertentu. == 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}} [[Kategori:Komputasi]] [[Kategori:Matematika ~~Diskrit~~diskrit]] ~~[[en:Automata Theory]]~~