SATUAN ACARA PERKULIAHAN (SAP)
Nama Mata Kuliah
: Teori Bahasa dan Automata
Kode Mata Kuliah
: TI 12A & TI 12B
Bobot Kredit
: 3 SKS
Semester Penempatan
: III
Penanggung Jawab Mata Kuliah
: Fathiah, ST. M. Eng.
Pertemua n/Minggu
1
2
3
Pokok Bahasan / Tujuan Instruksional Umum (TIU) 1. Bahasa dan Tatabahasa Formal TIU : Mahasiswa memahami konsep dan istilah yang umum digunakan dalam Teori Bahasa dan Otomata 2. Bahasa dan Tata bahasa Formal (lanjutan) TIU: Mahasiswa memahami tipe-tipe bahasa dan menganalisa tipetipe bahasa
3. Pengenalan Kompilasi
Sub Pokok Bahasan dan Sasaran Belajar/ Tujuan Instruksional Khusus (TIK)
1.1. Komponen Tatabahasa Formal - Mahasiswa dapat menjelaskan konsep-konsep : karakter, string, kata, token,kalimat, bahasa - Mahasiswa dapat memberi contoh tata bahasa menggunakan istilah –istilah simbol terminal, non terminal, produksi, derivasi - Mahasiswa dapat menyimpulkan bahwa setiap bahasa dibangun oleh suatu tatabahasa formal 2.1. Klasifikasi Tatabahasa Formal menurut Chomsky. - Mahasiswa dapat menjelaskan perbedaan dan sifat khusus keempat tatabahasa : unrestricted, context sensitive, context free, regular - Mahasiswa dapat memberi contoh setiap bahasa yang termasuk kelas setiap tata bahasa Chomsky - Mahasiswa dapat menyimpulkan bahwa setiap tata 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.1. Umum - 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
Teknik Pembelaj aran
Media Pembelaja ran
Evaluasi
Refe rensi
Ceramah
OHP dan Papan Tulis
1
Ceramah
OHP dan Respon Papan Tulis Bahasa dan Tatabahas a Formal
1
Ceramah
OHP dan Respon Papan Tulis Bahasa dan Tatabahas a Formal
1
4
4. Pengenalan Automata Hingga (AH) dan Ekspresi Regular (ER) TIU: Mahasiswa memahami AH dari suatu bahasa
5
5. Lebih lanjut tentang
dilakukan kompilator pada fase sintesa (pembentukan dan optimalisasi kode) - Mahasiswa dapat menentukan produksi yang left maupun right recursion dari suatu tatabahasa - Mahasiswa dapat menyebutkan hubungan associativity dan recursion - Mahasiswa dapat menentukan tata bahasa yang left /right associative 3.6. Ambigous Grammar - Mahasiswa dapat menentukan grammar yang ambigous 4.1. Automata Hingga Deterministik (AHD) - Mahasiswa dapat menjelaskan definisi AHD sebagai pasangan 5 tuple - Mahasiswa dapat menyajikan AHD dalam bentuk tabel dari bentuk graf yang diketahui dan sebaliknya. - 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.1. Automata Hingga Non-deterministik (AHN) - Mahasiswa dapat menjelaskan konsep AHN
Ceramah
OHP dan Papan Tulis
1
Ceramah dan
OHP dan Makalah Papan Tulis
1
Automata Hingga
6
7 8
- Mahasiswa dapat menjelaskan perbedaan AHD dengan AHN TIU: - Mahasiswa dapat menyajikan AHN dengan graf dan Mahasiswa tabel memahami - Mahasiswa dapat menjalankan AHN yang diberikan jenis-jenis Otomata untukmengenal string w Hingga 5.2. Transformasi AHN menjadi AHD dan konsep - Mahasiswa dapat membentuk AHD yang ekivalen ekivalensi antar jenis dengan suatu AHN yang diberikan tersebut 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 5.4. Equivalensi Grammar Regular (GR) dengan AH tentang - Mahasiswa dapat membuat transformasi himpunan Automata Hingga produksi pada GR menjadi fungsi transisi pada AHN (lanjutan) - Mahasiswa dapat membuat transformasi fungsi transisi pada AHD menjadi himpunan produksi pada GR TIU: 5.5. Equivalensi ER dan AHN-ε Mahasiswa dapat - Mahasiswa dapat membentuk graf AHN-ε jika merancang AH dari diketahui ER suatu bahasa UJIAN TENGAH SEMESTER 5. Lebih lanjut 5.6. Automata Hingga dengan Otput (AHO) tentang - Mahasiswa dapat menyajikan AHO dalam konsep Automata Hingga mesin Moore maupun Mealy (lanjutan) - Mahasiswa dapat menunjukkan ekivalensi dari mesin
diskusi
Ceramah dan diskusi
OHP dan Makalah Papan Tulis
1
Ceramah dan diskusi
OHP dan Makalah Papan Tulis
1
9
TIU: Mahasiswa dapat merancang AH dari suatu bahasa 6. Bentuk Normal Chomsky (BNC) TIU: Mahasiswa dapat menentukan BNC dari sembarang tata bahasa context free.
10
11
7. Pushdown Automata (PDA)
Moore dan Mealy - Mahasiswa dapat merancang AHO untuk masalah yang sederhana
6.1 Pengertian dasar - Mahasiswa dapat mengidentifikasikan alasan BNC dilakukan kepada context free - Mahasiswa dapat menjelaskan perbedaan antara BNCdengan 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 - Mahasiswa dapat menjelaskan definisi PDA - Mahasiswa dapat menjalankan PDA yang diberikan untuk mengenal string w
TIU: Mahasiswa dapat merancang PDA dari suatu bahasa 8. Ekivalensi 8.1. Membentuk PDA dari tata bahasa context free yang Pushdown diketahui
Ceramah dan diskusi
OHP dan Makalah Papan Tulis
1
Ceramah dan diskusi
OHP dan Makalah Papan Tulis
1
Ceramah dan
OHP dan Makalah Papan Tulis
1
Automata (PDA) dan bahasa context free
12 & 13
TIU: Mahasiswa memahami ekivalensi anatara mesin PDA dan bahasa bahasa context free 9. Grammar Context Free dan Parsing TIU: Mahasiswa memahami konsep parsing
- 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
diskusi
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 - 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
Ceramah dan diskusi
OHP dan Makalah Papan Tulis
1
14
15
10. Mesin Turing TIU: Mahasiswa mengenal, dapat menjalankan, dan dapat membuat mesin Turing dari suatubahasa. 11. Linear Bounded Autmaton (LBA) TUI: Mahasiswa mengenal, dapat menjalan, dan dapat membuat Linear Bounded Automaton dari suatu bahasa
16
- 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 rekursif-kiri dan kaitannya dengan parsing top-down 10. Mesin turing (MT) - Mahasiswa dapat menjelaskan definisi MT - Mahasiswa dapat menjelaskan hubungannya dengan bahasa unrestricted - Mahasiswa dapat menjalankan MT sebagai pengenal suatu bahasa - Mahasiswa dapat membuat mesin Turing dari suatu bahasa 11.1 Linear Bounded Autmaton (LBA) - Mahasiswa dapat menjelaskan definisi LBA - 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
UJIAN AKHIR SEMESTER
Referensi: Sediyono, Edi. Teknik Kompilasi Teori dan Praktik. Penerbit Andi
Ceramah dan diskusi
OHP dan Makalah Papan Tulis
1
Ceramah dan diskusi
OHP dan Makalah Papan Tulis
1
