SATUAN ACARA PERKULIAHAN MATA KULIAH : TEORI BAHASA DAN AUTOMATA (TBA) KODE / SKS : KK-045325 / 3 SKS Mingu ke 1.
Pokok Bahasan Dan TIU 1. Pendahuluan TIU : Mahasiswa dapat menjelaskan konsep dasar bahasa dan teori tentang string
Sub Pokok Bahasan dan Sasaran Belajar 1.1. Teori Bahasa • Mahasiswa dapat memahami pengertian bahasa formal 1.2. Automata • Mahasiswa dapat memahami pengertian automata 1.3. Beberapa pengertian dasar • Mahasiswa dapat menjelaskan pengertian-pengertian : simbol, string, panjang string, dan simbol / string hampa 1.4. Operasi dasar string • Mahasiswa dapat menjelaskan operasi-operasi dasar string : prefix, proper prefix, postfix / sufix, proper psotfix / sufix, head, tail, substring, proper substring, subsequence, proper subsequence, concatenation, alternation, Kleene clossure, dan positive clossure. 1.5. Beberapa sifat operasi string • Mahasiswa dapat menjelaskan beberapa sifat operasi dasar string, sifat aljabar concatenation, sifat aljabar alternation, dan beberapa kesamaan Kleene / positive clossure.
2. Grammar dan Bahasa TIU : Mahasiswa dapat menjelaskan beberapa terminologi khusus grammar dan bahasa
2.1. Konsep dasar • Mahasiswa dapat memahami konsep : alfabet, simbol terminal, kalimat, bahasa, lambang simbol terminal, lambang simbol non terminal, lambang simbol terminal/non terminal, lambang string simbol terminal, lambang string simbol terminal/non terminal, lambang dan pengertian produksi, lambang dan pengertian derivasi, sentensial dan kalimat. • Mahasiswa dapat memahami 4 komponen grammar
Cara Pengajaran Kuliah mimbar
Media Papan tulis, OHP
Tugas
Referensi 1
Mingu ke 2.
Pokok Bahasan Dan TIU 2. Grammar dan Bahasa (lanjutan) TIU : Mahasiswa dapat memahami 4 kelas grammar Chomsky
3.
2.
Grammar dan Bahasa (lanjutan)
4.
TIU : Mahasiswa dapat menentukan grammar sebuah bahasa dan mengetahui mesin pengenal bahasa 3. Mesin Turing TIU : Mahasiswa dapat menjelaskan mesin turing sebagai mesin pengenal bahasa
Sub Pokok Bahasan dan Sasaran Belajar 2.2. Klasifikasi Chomsky • Mahasiswa dapat menjelaskan menjelaskan 4 tipe grammar chomsky • mahasiswa dapat menentukan tipe sebuah grammar melalui analisa terhadap himpunan produksi yang diberikan
Cara Pengajaran Kuliah mimbar
Media
Tugas
Papan tulis, OHP
Referensi 1, 2
2.3. Penentuan bahasa berdasarkan grammar • Mahasiswa dapat melakukan derivasi kalimat dan menentukan bahasanya berdasarkan grammar yang diberikan 2.4. Penentuan grammar sebuah bahasa • Mahasiswa dapat membuat grammar suatu bahasa
Kuliah mimbar
Papan tulis, OHP
Kuliah mimbar
Papan tulis, OHP
2.5. Mesin pengenal bahasa • Mahasiswa dapat mengenal nama-nama mesin yang terkait dengan masing-masing kelas bahasa
3.1. Komponen “fisik” mesin turing • Mahasiswa dapat membuat ilustrasi mesin turing, menyebutkan setiap komponennya, dan menjelaskan sifat / kemampuan setiap komponen tersebut
Pekerjaan rumah : • penentuan bahasa berdasarkan grammar • penentuan grammar suatu bahasa
1, 2
1, 2
3.2. Ilustrasi mesin turing dalam graf berarah • Mahasiswa dapat menjelaskan pengertian node, edge, serta bobot edge dari mesin turing • Mahasiswa dapat menjelaskan proses pembacaan mesin turing terhadap string masukan 3.3. Merancang sebuah mesin turing pengenal bahasa • Mahasiswa dapat menyusun algoritma proses pengenalan bahasa tertentu oleh mesin turing • Mahasiswa dapat mengimplementasikan algoritma tersebut sebagai sebuah graf mesin turing
2
Mingu ke
Pokok Bahasan Dan TIU
Sub Pokok Bahasan dan Sasaran Belajar
Cara Pengajaran
Media
Tugas
Referensi
3.4. Tracing string oleh mesin turing • Mahasiswa dapat melakukan tracing string oleh mesin turing 5
4. Automata Hingga TIU : Mahasiswa dapat menjelaskan definisi automata hingga (AH), autota hingga deterministik (AHD), dan automata hingga non deterministik (AHN)
4.1. Automata Hingga (AH) • Mahasiswa dapat menjelaskan definisi AH melalui keempat pasangan tuple-nya • Mahasiswa dapat menjelaskan perbedaan antara automata hingga deterministik (AHD) dan automata non deterministik (AHN) terutama mengenai sifat fungsi transisinya
Kuliah mimbar
Papan tulis, OHP
1, 2
Kuliah mimbar
Papan tulis, OHP
1, 2
4.2. Automata Hingga Deterministik (AHD) • Mahasiswa dapat menyatakan fungsi transisi AHD dalam bentuk tabel • Mahasiswa dapat membuat ilustrasi graf untuk sebuah AHD • Mahasiswa dapat menguji penerimaan / penolakan sebuah string oleh AHD melalui tracing 4.3. Equivalensi 2 AHD • Mahasiswa dapat memahami algoritma uji kesamaan 2 buah AHD
6
4. Automata Hingga (lanjutan) TIU : Mahasiswa dapat menjelaskan definisi mesin stata hingga, menyatakannya sebagai tabel atau graf, menyatakan penjumlah biner dalam mesin stata hingga, serta memahami ekspresi regular
4.4. Mesin Stata Hingga (MSH) • Mahasiswa dapat menjelaskan definisi MSH melalui keenam pasangan tuple-nya • Mahasiswa dapat menyatakan MSH dalam ungkapan tabel dan graf 4.5. Mesin Stata Hingga Penjumlah Biner • Mahasiswa dapat memahami sifat penjumlahan biner, baik dalam moda carry atau not carry • Mahasiswa dapat membangun mesin stata hingga dari keteraturan penjumlahan biner • Mahasiswa dapat membuat graf mesin stata hingga penjumlah biner • Mahasiswa dapat melakukan penjumlahan biner melalui tracing terhadap mesin stata hingga penjumlah biner
3
Mingu ke
7
Pokok Bahasan Dan TIU
4. Automata Hingga (lanjutan) TIU : Mahasiswa dapat menjelaskan sifat-sifat automata hingga non deterministik (AHN) dan AHN dengan transisi hampa (AHNε)
Sub Pokok Bahasan dan Sasaran Belajar 4.6. Ekspresi Regular • Mahasiswa dapat menyatakan bahasa regular sebagai ekspresi regular • Mahasiswa dapat membuktikan kesamaan dua buah ekspresi regular 4.7 Automata Hingga Nondeterministik (AHN) • Mahasiswa dapat membuat tabel fungsi transisi AHN • Mahasiswa dapat mengimplementasikan tabel transisi AHN ke dalam bentuk graf • Mahasiswa dapat menguji penerimaan / penolakan sebuah string oleh AHN melalui tracing • Mahasiswa dapat melakukan perluasan sifat-sifat fungsi transisi AHN • Mahasiswa dapat menjelaskan dua alternatif kriteria penerimaan sebuah string oleh AHN
Cara Pengajaran
Media
Tugas
Referensi
Kuliah mimbar
Papan tulis, OHP
1, 2
Kuliah mimbar
Papan tulis, OHP
1, 2
4.7.a. AHN dengan transisi hampa (AHN-ε) • Mahasiswa dapat menjelaskan pengertian AHN-ε • Mahasiswa dapat memberikan contoh-contoh bahasa yang ekuivalen dengan AHN-ε 8
4. Automata Hingga (lanjutan) TIU : Mahasiswa dapat menjelaskan ekuaivalensi AHN, AHD, dan GR serta antara ER dengan AHN-ε
4.8. Ekuivalensi AHN, AHD, dan GR (Grammar Regular) • Mahasiswa mengetahui ada transformasi siklis AHN – AHD – GR – AHN • Mahasiswa dapat menjalankan algoritma pembentukan AHD dari AHN • Mahasiswa dapat menjalankan algoritma pembentukan GR dari AHD • Mahasiswa dapat menjalankan algoritma pembentukan AHN dari GR 4.9. Ekuivalensi AHN-ε dengan ER (Ekspresi Regular) • Mahasiswa dapat menjelaskan bentuk-bentuk dasar ER dan AHN-ε yang ekuivalen dengannya • Mahasiswa dapat membuat graf AHN-ε yang ekuivalen dengan sebuah ER
4
Mingu ke 9
Pokok Bahasan Dan TIU 5. Grammar Context Free dan Parsing TIU : Mahasiswa dapat menjelaskan proses parsing
Sub Pokok Bahasan dan Sasaran Belajar 5.1. Hal Umum Tentang Parsing • Mahasiswa dapat melakukan parsing • Mahasiswa dapat membuktikan kalimat ambigu
Cara Pengajaran Kuliah mimbar
Media Papan tulis, OHP
Tugas Pekerjaan Rumah : Parsing GPS
Referensi 1, 2
5.2. Metoda Parsing • Mahasiswa dapat menjelaskan kedua jenis parsing, yaitu parsing top-down dan bottom-up 5.3. Parsing Top-down • Mahasiswa dapat menjelaskan metoda Brute-Force • Mahasiswa dapat menjelaskan metoda Recursive-Descent 5.4. Parsing Bottom-up • Mahasiswa dapat menjelaskan Relasi Preseden dan Grammar Preseden Sederhana (GPS) • Mahasiswa dapat membuat tabel preseden • Mahasiswa dapat melakukan parsing GPS
10
6. Bentuk Normal Chomsky TIU : Mahasiswa dapat melakukan transformasi grammar context free ke bentuk normal Chomsky
6.1. Bentuk Normal Chomsky • Mahasiswa dapat mengetahui bentuk normal Chomsky • Mahasiswa dapat mengetahui empat langkah transformasi grammar context free ke bentuk normal Chomsky
Kuliah mimbar
Papan tulis, OHP
1, 2
6.2. Eliminasi produksi hampa • Mahasiswa dapat memahami pengertian simbol nullable • Mahasiswa dapat melakukan eliminasi simbol nullable 6.3. Eliminasi produksi unitas • Mahasiswa dapat memahami pengertian produksi unitas • Mahasiswa dapat melakukan eliminasi produksi unitas 6.4. Batasan Bentuk Ruas Kanan Produksi • Mahasiswa dapat merubah produksi ke bentuk bakunya 6.5. Batasan Panjang Ruas Kanan Produksi • Mahasiswa dapat mereduksi produksi ke panjang bakunya
5
Mingu ke 11
Pokok Bahasan Dan TIU 7. Automata Pushdown (PDA) TIU : Mahasiswa dapat menjelaskan PDA dan melakukan tracing kalimat dengan PDA
12
8. Pengenalan Compiler TIU : Mahasiswa dapat menjelaskan urutan proses kompilasi
Sub Pokok Bahasan dan Sasaran Belajar 7.1. Definisi Automata Pushdown (PDA) • Mahasiswa dapat menjelaskan definisi APD melalui 7 pasangan tuple-nya • Mahasiswa dapat menyatakan fungsi transisi PDA ke dalam bentuk tabel
Cara Pengajaran Kuliah mimbar
Media
Tugas
Referensi
Papan tulis, OHP
1, 2
Papan tulis, OHP
1, 2
7.2. Tracing oleh PDA • Mahasiswa dapat melakukan tracing untuk membuktikan penerimaan atau penolakan suatu string oleh PDA • Mahasiswa dapat menjelaskan dua kondisi penerimaan string oleh PDA yaitu accept by final state dan accepted by empty stack 7.2. Deterministik PDA dan Nondeterministik PDA • Mahasiswa dapat menjelaskan perbedaan PDA deterministik dan PDA nondeterministik 8.1. Translator • Mahasiswa dapat memahami pengertian translator serta compiler sebagai salah satu bentuk traslator
Kuliah mimbar
8.2. Proses Kompilasi • Mahasiswa dapat menjelaskan fase-fase kompilasi serta halhal yang dilakukan pada setiap fase tersebut.
DAFTAR REFERENSI 1. D. Suryadi H.S. Pengantar Automata Bahasa Formal dan Kompilasi. Seri Diktat Kuliah. Penerbit Gunadarma. 2. Asep Juarna. http://staffsite.gunadarma.ac.id/ajuarna/stuffing/ndex.php?stateid=stuff
6
