SATUAN ACARA PERKULIAHAN (SAP) Nama Mata Kuliah Kode Mata Kuliah Bobot Kredit Semester Penempatan Kedudukan Mata Kuliah Mata Kuliah Prasyarat Penanggung Jawab Mata Kuliah
Pertemuan
Pokok Bahasan /
/ Minggu
Tujuan Instruksional Umum (TIU)
1
2
2
: : : : : : :
Teori Bahasa dan Automata TI 014 3 SKS III Mata Kuliah Keilmuan dan Keterampilan Asrul, ST
Sub Pokok Bahasan dan Sasaran Belajar / Tujuan Instruksional Khusus (TIK)
1.
Tehnik Pembelajara n
Bahasa dan Tatabahasa 1.1. Komponen Tatabahasa Formal Ceramah Formal - Mahasiswa dapat menjelaskan konsep-konsep : karakter, string, kata, token,kalimat, bahasa TIU : - Mahasiswa dapat memberi contoh tata bahasa Mahasiswa memahami menggunakan istilah –istilah simbol terminal, non konsep dan istilah yang terminal, produksi, derivasi umum digunakan dalam - Mahasiswa dapat menyimpulkan bahwa setiap bahasa Teori Bahasa dan Otomata dibangun oleh suatu tatabahasa formal 2. Bahasa dan Tata bahasa 2.1. Klasifikasi Tatabahasa Formal menurut Chomsky. Ceramah Formal (lanjutan) - Mahasiswa dapat menjelaskan perbedaan dan sifat khusus keempat tatabahasa : unrestricted, context TIU: sensitive, context free, regular Mahasiswa memahami tipe- Mahasiswa dapat memberi contoh setiap bahasa yang tipe bahasa dan termasuk kelas setiap tata bahasa Chomsky menganalisa tipe-tipe - Mahasiswa dapat menyimpulkan bahwa setiap tata bahasa bahasa yang tingkatannya lebih tinggi juga merupakan tata bahasa yang lebih rendah (misalnya tata bahasa regular juga adalah tata bahasa contextsensitive) - Mahasiswa dapat menentukan tatabahasa dari bahasa yang diberikan dan sebaliknya. 3. Pengenalan Kompilasi 3.1. Umum Ceramah
1
Media Pembelajara Evaluasi
Referensi
n Papan Tulis & OHP
Membuat contoh bahasa dan tata bahasa
1
Papan Tulis & OHP
1
Papan Tulis &
1
- Mahasiswa dapat menjelaskan proses kompilasi, fase analisisnya, dan fase sintesisnya 3.2. Fase analisa - Mahasiswa dapat menjelaskan semua hal yang dilakukan kompilator pada fase analisa (leksikal, sintaks, dan semantik) 3.3. Fase sintesa - Mahasiswa dapat menejelaskan semua hal yang dilakukan kompilator pada fase sintesa (pembentukan dan optimalisasi kode) 4. Pengenalan Automata 4.1. Automata Hingga Deterministik (AHD) Ceramah Hingga (AH) dan Ekspresi - Mahasiswa dapat menjelaskan definisi AHD Regular (ER) sebagai pasangan 5 tuple - Mahasiswa dapat menyajikan AHD dalam bentuk TIU: tabel dari bentuk graf yang diketahui dan Mahasiswa memahami AH sebaliknya. dari suatu bahasa - Mahasiswa dapat menjalankan AHD yang diberikan untuk mengenal suatu untai dan menyimpulkan diterima tidaknya untai tersebut oleh AHD tersebut. - Mahasiswa dapat menentukan bahasa yang diterima oleh suatu AHD - Mahasiswa dapat mengikhtisarkan ekivalensi AHD dan bahasa regular 4.2. Ekspresi Regular (ER) - Mahasiswa dapat menarik kesimpulan mengenai equivalensi antara bahasa regular dengan ekspresi regular. - Mahasiswa dapat menjelaskan definisi rekursif ER - Mahasiswa dapat melakukan operasi pada ER : concate, alternate dan clossure (Kleene dan positive) 5. Lebih lanjut tentang 5.1. Automata Hingga Non-deterministik (AHN) Ceramah Automata Hingga - Mahasiswa dapat menjelaskan konsep AHN - Mahasiswa dapat menjelaskan perbedaan AHD TIU: dengan AHN Mahasiswa memahami - Mahasiswa dapat menyajikan AHN dengan graf jenis-jenis Otomata Hingga dan tabel dan konsep ekivalensi antar - Mahasiswa dapat menjalankan AHN yang
OHP
TIU: Mahasiswa memahami hubungan bahasa formal dan proses kompilasi
3
4
2
Papan Tulis & OHP Diskusi
Papan Tulis & OHP
Membuat Bahasa dan merumusk an ekspresi regulerny
1
1
jenis tersebut
5
6.
7
diberikan untuk mengenal string w 5.2. Transformasi AHN menjadi AHD - Mahasiswa dapat membentuk AHD yang ekivalen dengan suatu AHN yang diberikan 5.3. AHN dengan transisi hampa (AHN-ε) - Mahasiswa dapat menjelaskan konsep AHN-ε - Mahasiswa dapat menjelaskan perbedaan antara AHD, AHN dan AHN-ε) - Mahasiswa dapat menyajikan AHN-ε dalam graf maupun tabel - Mahasiswa dapat menjalankan AHN-ε yang diberikan untuk mengenal string w - Mahasiswa dapat membentuk AHN yang ekivalen dengan suatu AHN-ε yang diberikan 5. Lebih lanjut tentang 5.4. Equivalensi Grammar Regular (GR) dengan AH Automata Hingga (lanjutan) - Mahasiswa dapat membuat transformasi himpunan produksi pada GR menjadi fungsi transisi pada TIU: AHN Mahasiswa dapat - Mahasiswa dapat membuat transformasi fungsi merancang AH dari suatu transisi pada AHD menjadi himpunan produksi bahasa pada GR 5.5. Equivalensi ER dan AHN-ε - Mahasiswa dapat membentuk graf AHN-ε jika diketahui ER -
Ceramah
Diskusi
5. Lebih lanjut tentang 5.6. Automata Hingga dengan Otput (AHO) Automata Hingga (lanjutan) - Mahasiswa dapat menyajikan AHO dalam konsep mesin Moore maupun Mealy TIU: - Mahasiswa dapat menunjukkan ekivalensi dari Mahasiswa dapat mesin Moore dan Mealy merancang AH dari suatu - Mahasiswa dapat merancang AHO untuk masalah bahasa yang sederhana
Ceramah
6. Bentuk Normal Chomsky 6.1 Pengertian dasar (BNC) - Mahasiswa dapat mengidentifikasikan alasan BNC dilakukan kepada context free TIU: - Mahasiswa dapat menjelaskan perbedaan antara
Ceramah
3
Papan Tulis & OHP
Papan Tulis & OHP Diskusi
Papan Tulis & OHP
Membuat Bahasa dan Rumus Tata Bahasany a
1
Membuat suatu bahasa dari Automata hingga peneriman ya
2,5
1
Mahasiswa dapat menentukan BNC dari sembarang tata bahasa context free.
8
7. Pushdown Automata (PDA) TIU: Mahasiswa dapat merancang PDA dari suatu bahasa
9
10
8. Ekivalensi Pushdown Automata (PDA) dan bahasa context free TIU: Mahasiswa memahami ekivalensi anatara mesin PDA dan bahasa bahasa context free 9. Grammar Context Free dan Parsing TIU: Mahasiswa memahami konsep parsing
BNC dengan tata bahasa regular yang mempunyai kemiripan dengan BNC - Mahasiswa dapat menunjukkan simbol nullable, dan produksi unitas 6.2 Empat langkah normalisasi - Mahasiswa dapat membentuk BNC dari sembarang context free malalui 4 langkah berikut: • langkah I : berkaitan dengan eliminasi simbol nullable • langkah II : berkaitan dengan eliminasi produksi unitas dan pembangkitan produksi lain yang terkait • langkah III : mengarah ke bentuk {A → a, A → B1B2B3 ... Bn, n > 1} • langkah IV : mengarah ke bentuk {A → a, A → B1B2} 7.1 Definisi Ceramah - Mahasiswa dapat menjelaskan definisi PDA - Mahasiswa dapat menjalankan PDA yang diberikan untuk mengenal string w
Papan Tulis & OHP
Exercises 12.1 12.3 hal. 230 ref 2.
Ref 2 hal 213-231
Exercises 13.1, 13.2 hal. 242, 243 ref 2.
Ref 2 hal 232-243
8.1. Membentuk PDA dari tata bahasa context free yang diketahui - Mahasiswa dapat membuat PDA yang ekivalen dengan tatabahasa context free yang diberikan 8.2. Membentuk tata bahasa context free dari PDA yang diketahui - Mahasiswa dapat membuat tatabahasa context free yang ekivalen dengan PDA yang diberikan
Ceramah
Papan Tulis & OHP
9.1. Terminologi Sintaks - Mahasiswa dapat membuat pohon sintaks - Mahasiswa dapat mengidentifikasin sentensial, phrase, simple phrase, dan handle dari suatu tata bahasa. 9.2. Parsing
Ceramah
Papan Tulis & OHP
4
1
-
Mahasiswa dapat menjelaskan definsi parsing Mahasiswa mengenal bagian-bagian dari pohon sintaks - Mahasiswa dapat membentuk kalimat dengan pohon sintaks - Mahasiswa dapat menentukan sentensial dalam suatu pohon sintaks - Mahasiswa dapat menjelaskan kaitan antara derivasi dengan pohon sintaks 9.3. Sifat Ambiguous - Mahasiswa dapat menjelaskan pengertian ambiguous bagi kalimat maupaun tata bahasa - Mahasiswa dapat menjelaskan kelemahan kalimat ambiguous - Mahasiswa dapat mengusahakan perbaikan grammar ambiguous jika memungkinkan 9.4. Teknik-teknik Parsing - Mahasiswa dapat menunjukkan perbedaan antara parsing top-down dengan parsing bottom-up - Mahasiswa dapat menunjukkan perbedaan parsing top-down dengan backup dan tanpa backup - Mahasiswa dapat menunjukkan perbedaan parsing top-down backup teknik Brute-Force dengan recursive descent - Mahasiswa dapat menjelaskan pengertian rekursifkiri dan kaitannya dengan parsing top-down UJIAN TENGAH SEMESTER
11 12 & 13
11. Mesin Turing
Papan Tulis & OHP
Mahasiswa mengenal, dapat menjalankan, dan dapat membuat mesin Turing dari suatu bahasa.
11. Mesin turing (MT) Ceramah - Mahasiswa dapat menjelaskan definisi MT & kerja - Mahasiswa dapat menjelaskan hubungannya klompok dengan bahasa unrestricted - Mahasiswa dapat menjalankan MT sebagai pengenal suatu bahasa - Mahasiswa dapat membuat mesin Turing dari suatu bahasa
Membuat M. Turing untuk mengenal bahasa tertentu.
12. Linear Bounded Autmaton (LBA)
11.2 Linear Bounded Autmaton (LBA) - Mahasiswa dapat menjelaskan definisi LBA
Papan Tulis & OHP
Membuat LBA
TIU:
14 & 15
5
Ceramah
2, 5
Mahasiswa mengenal, dapat menjalan, dan dapat membuat Linear Bounded Automaton dari suatu bahasa 16
-
Mahasiswa dapat menjelaskan hubungan LBA dengan bahasa context sensitive Mahasiswa dapat menjelaskan LBA sebagai pengenal suatu bahasa Mahasiswa dapat membuat LBA untuk mengenal bahasa tertentu
& kerja kelompok
untuk mengenal bahasa tertentu
UJIAN AKHIR SEMESTER
Referensi : 1. D. Suryadi HS. Pengantar Automata Bahasa Formal dan Kompilasi. Penerbit Gunadarma. 2. Martin, John C., Introduction to Languages and the Theory of Computaion, McGraw-Hill Inc, Singapore, 1991 3. Tremblay, Jean-Paul, Paul G. Sorenson, The Theory and Practice of Compiler, McGraw-Hill Co, New York, 1985 4. Kelley, Dean, Otomata dan Bahasa-bahasa Formal, PT. Prenhallindo. 5. Hopcroft, John E., Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison Wesley Publishing Company, Reading, Massachusetts, 1979.
6
