imambukhari.weebly.com · web viewapa itu otomata dan kompilasi ? otomata adalah model. model dari...

Dasar Teori Otomata & Bahasa·Dasar Teori Otomata & Kompilasi·Komponen Ilmu Informatika·Model Mesin Komputasi & Pemanfaatan Otomata danTeori Bahasa

© Imam Bukhari, S.Kom, M.M.

Apa itu Otomata dan Kompilasi ?Otomata adalah MODEL. Model dari sistem apapun

yang akan kita komputasikan.Tidak ada bidang apapun dalam teknologi informasi

yang tidak terkait dengan teori ‘Otomata’ ini.Semua bentuk sistem, diskrit, kontinu, bahkan hybrid

(gabungan event diskrit dan kontinu dalam satusistem) dapat dimodelkan oleh teori ‘Otomata’ ini.Sementara, Kompilasi adalah ilmu yang mempelajari

bagaimana kita dapat merancang & membangunbahasa pemrograman.

Kompilasi merupakan SALAH SATU bidang yangmemanfaatkan teori ‘otomata’ ini.


Komponen Ilmu InformatikaSub bidang apapun dalam ilmu informatika pasti memiliki 2 komponen :

1. Ide/gagasan dirupakan ke dalam bentuk MODEL KOMPUTASIBeberapa disiplin ilmu yang diadopsi : Neuron Nets Finite Automata Sistem Logika Formal Sistem Tata Bahasa

Proof MethodsPsycho-Linguistic:1. Apakah arti bahasa itu ?2. Bagaimana manusia mengembangkan bahasa ?3. Bagaimana manusia memahami bahasa ?4. Bagaimana manusia mengajarkan bahasa ke anak-anaknya ?5. Bagaimana cara menyatakan gagasan ?6. Bagaimana manusia membangun kalimat dari gagasan yang

ada dalam pikirannya ?

2. Teknik rekayasa untuk mengimplementasikan model ke dalam sebuah

bentuk sistem yang terkomputasi (programming/coding)

Perkembangan Teori OtomataNoam Chomsky, membuat model matematis untuk mendeskripsikan bahasa

sekaligus menjawab pertanyaan ttg psycho-linguistic membuat perangkat formal untuk memodelkan properti

bahasa (disebut Grammar)

McCulloch & Pitts, merancang Finite Automata untuk memodelkan neuronnets

Stephen Kleene, menemukan model representasi lain dari automata melaluiRegular Expression

Alan Turing, menemukan model untuk mengidentifikasi apakah sebuahpermasalahan dapat dikomputasi Mesin Turing


Model Komputasi Awal & SekarangModel Komputasi Awal :

CPU

Model Komputasi Sekarang :

Memori Sementara

Memori

Memori Keluaran CPU Memori Masukan

Memori Program


Bagaimana proses komputasi untuk :

f(x) = x + x + x


1) Memori Sementara 3) Memori Sementaraz = 3 + 3 = 6

f(x) = z + 3 = 9

Memori Keluaran CPU Memori Masukan Memori Keluaran CPUMemori Masukan

misal, x = 3

Memori Program

hitung x + xhitung 2x + x

Memori Program


2) Memori Sementara 4)Memori Sementara

z = 3 + 3 = 6f(x) = z + 3 = 9

Memori Keluaran CPUMemori Masukan

misal, x = 3

Memori Keluaran

f(x) = 9CPU

Memori Masukan

misal, x = 3

Memori Program



Memori Program


Model Mesin Komputasi3 model mesin komputasi yang akan kita pelajari dalam otomata(berdasarkan jenis memori yang dimilikinya) :1. Finite Automata (FA)

Tidak memiliki memori sementara. Finite merupakan kelasmachine dengan kemampuan paling terbatas. Contoh : VendingMachine.

2. Pushdown Automata (PDA)Memiliki memori sementara dengan mekanisme LIFO (Last In FirstOut,yaitu mekanisme stack). Contoh : Bahasa pemrograman tingkatmenengah.

3. Turing Machine (TM)Memiliki memori dengan mekanisme pengaksesan acak (randomaccess memory) contoh: bahasa pemrograman tingkat tinggi,Komputer saat ini.


Pemanfaatan Model Mesin Komputasi1. Finite Automata & Ekspresi Regular

Dimanfaatkan untuk merancang lexical analyzer, yaitubagian kompilator yang bertugas mengelompokkankarakter-karakter menjadi token-token yaitu unitbahasa terkecil seperti keyword, identifier, dsb.

Contoh :a. terdapat pada editor teksb. pengenalan / pencarian polac. pengolahan teksd. pencarian teks beragam file (grep, fgrep, egrep diLinux)e. aplikasi pembedaan file.

Pemanfaatan Model Mesin Komputasi2. Pushdown Automata & Context Free Grammar

Dimanfaatkan untuk mengenali spesifikasi bahasapemrograman komputer( pemrograman markup, kamusdata, query, script, parsing, dll). Dalam parsingdimanfaatkan untuk memeriksa kebenaran sintaksprogram

3. Turing MachineUntuk mengidentifikasi ketidakmungkinan penulisanprogram untuk dapat dikomputasi oleh mesin komputasiapapun.

Urutan Operator KeteranganI ^ PangkatII *, / Kali, BagiIII +, - Tambah, Kurang

Tugas Mingguan 1 Buat, kerjakan & kumpulkan tugas I tentang ilustrasi

kerja model komputasi untuk perhitungan fungsi :1. f(x) = x3 + X2 + 4x + 52. g(x) = x2 – 6x + 93. h(x) = (2x + 4) (3y + 6)


54)( xxxxf

Jawaban Tugas Mingguan 1 (Soal 1)3 2

· Langkah 1:▫ Memori Masukan: -▫ Memori Sementara: -▫ Memori Keluaran: -▫ Memori Program:

Hitung a = x * x Hitung b = a * x Hitung c = x * 4 Hitung d = b + a Hitung e = c + 5 Hitung f(x) = d + e


Jawaban Tugas Mingguan 1 (Soal 1)· Langkah 2:

▫ Memori Masukan: Misal x = 2

▫ Memori Sementara: -▫ Memori Keluaran: -▫ Memori Program:





▫ Memori Sementara: Hitung a = x * x = 4 Hitung b = a * x = 8 Hitung c = x * 4 = 8 Hitung d = b + a = 12 Hitung e = c + 5 = 13 Hitung f(x) = d + e =

15


▫ Memori Keluaran: -▫ Memori Program:




▫ Memori Sementara: Hitung a = x * x = 4 Hitung b = a * x = 8 Hitung c = x * 4 = 8 Hitung d = b + a = 12 Hitung e = c + 5 = 13 Hitung f(x) = d + e =

15

▫ Memori Keluaran:▫ f(x) = 25

▫ Memori Program: Hitung a = x * x Hitung b = a * x Hitung c = x * 4 Hitung d = b + a Hitung e = c + 5 Hitung f(x) = d + e

96)( xxxgJawaban Tugas Mingguan 1 (Soal 2)

2

· Langkah 1:▫ Memori Masukan: -▫ Memori Sementara: -▫ Memori Keluaran: -▫ Memori Program:

Hitung a = x * x Hitung b = 6 * x Hitung c = b + 9 Hitung g(x) = a - c




▫ Memori Sementara: -▫ Memori Keluaran: -▫ Memori Program:

Hitung a = x * x Hitung b = 6 * x Hitung c = b + 9 Hitung g(x) = a - c




▫ Memori Sementara: Hitung a = x * x = 4 Hitung b = 6 * x = 12 Hitung c = b + 9 = 21 Hitung g(x) = a – c =

17


▫ Memori Keluaran: -▫ Memori Program:

Hitung a = x * xHitung b = 6 * xHitung c = b + 9Hitung g(x) = a - c

Jawaban Tugas Mingguan 1· Langkah 4:


▫ Memori Sementara: Hitung a = x * x = 4 Hitung b = 6 * x = 12 Hitung c = b + 9 = 21 Hitung g(x) = a – c =

17


▫ Memori Keluaran:▫ g(x) = -17

▫ Memori Program:Hitung a = x * xHitung b = 6 * xHitung c = b + 9Hitung g(x) = a - c

imambukhari.weebly.com · web viewapa itu otomata dan kompilasi ? otomata adalah model. model dari...

Documents