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.

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

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)

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

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

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

Model Komputasi Awal & SekarangModel Komputasi Awal :

CPU

Model Komputasi Sekarang :

Memori Sementara

Memori

Memori Keluaran CPU Memori Masukan

Memori Program

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

Bagaimana proses komputasi untuk :

f(x) = x + x + x

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

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

hitung x + xhitung 2x + x

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

hitung x + xhitung 2x + x

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

Memori Program

hitung x + xhitung 2x + x

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.

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

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.

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

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.

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

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)

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

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

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

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

▫ Memori Masukan: Misal x = 2

▫ 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

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

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

▫ Memori Masukan: Misal x = 2

▫ 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

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

▫ 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 2)· Langkah 4:

▫ Memori Masukan: Misal x = 2

▫ 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

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

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

▫ Memori Masukan: Misal x = 2

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

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

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

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

▫ Memori Masukan: Misal x = 2

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

17

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

▫ 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 Masukan: Misal x = 2

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

17

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

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

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