Postingan

Tugas Teknik Kompilasi - finite state automata

Gambar
Finite State Automata Finite state automata adalah mesin abstrak berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata. Finite State Automata (FSA) adalah model matematika yang dapat menerima input dan mengeluarkan output yang memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasarkan input dan fungsi transisi. Finite state automata tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini. Finite State Automata dinyatakan oleh pasangan 5 tuple, yaitu: M=(Q , Σ , δ , S , F ) Q = himpunan state Σ = himpunan simbol input δ = fungsi transisi δ : Q × Σ S = state awal / initial state , S ∈ Q F = state akhir, F ⊆ Q Karakteristik Finite Automata 1.Setiap Finite Automata memiliki keadaan dan transisi yang terbatas. 2.Transisi dari satu keadaan ke keadaan lainnya dapat bersifat determ
Posting Komentar
Baca selengkapnya

Tugas Teknik Kompilasi - Push Down Automata (PDA)

Gambar
Push Down Automata (PDA) PDA adalah mesin otomata dari TBBK yang diimplementasikan dengan stack sehingga hanya terdapat operasi “push” dan “pop” Stack (tumpukan) adalah suatu struktur data yang menggunakan prinsip LIFO (Last In First Out). Sebuah stack selalu memiliki top of stack dan elemen-elemen stack itu yang akan masuk ke dalam stack dengan method “push” dan akan keluar dari stack dengan method “pop”. Definisi : PDA adalah pasangan 7 tuple M = (Q, Σ, , q  0  , Z  0  , δ, A), dimana : Q : himpunan hingga stata, Σ : alfabet input, : alfabet  stack , q  0  ∈ Q : stata awal, Z  0  ∈ : simbol awal  stack , A ⊆ Q : himpunan stata penerima, fungsi transisi δ : Q  (Σ ∪ {ε})     → 2  Q        *   (himpunan bagian dari Q    *) Untuk stata q ∈ Q, simbol input a ∈ Σ, dan simbol  stack  X∈ , δ(q, a, X) = (p, α) berarti : PDA bertransisi ke stata p dan mengganti X pada stack dengan string α. Konfigurasi PDA pada suatu saat dinyatakan sebagai triple (q, x, α), di
Posting Komentar
Baca selengkapnya

Tugas Teknik Kompilasi - Mesin Turing

Gambar
MESIN TURING Mesin Turing   adalah model komputasi teoritis yang ditemukan oleh   Alan Turing, berfungsi sebagai model ideal untuk melakukan perhitungan matematis. Walaupun model ideal ini diperkenalkan sebelum   komputer   nyata dibangun, model ini tetap diterima kalangan   ilmu komputer   sebagai model komputer yang sesuai untuk menentukan apakah suatu fungsi dapat selesaikan oleh komputer atau tidak (menentukan   computable function ). Mesin Turing terkenal dengan ungkapan " Apapun yang bisa dilakukan oleh Mesin Turing pasti bisa dilakukan oleh   komputer ." Sebuah mesin turing terdiri atas barisan sel tersusun berupa pita yang dapat bergerak maju mundur, komponen aktif baca/tulis pita yang memiliki status perhitungan serta dapat mengubah/menulisi sel aktif yang ada di pita tadi, dan suatu kumpulan instruksi bagaimana komponen baca/tulis ini harus melakukan modifikasi terhadap sel aktif pada pita, serta bagaimana menggerakkan pita tersebut. Pada setiap langkah
Posting Komentar
Baca selengkapnya