Tanggal Revisi : Tanggal :
Versi : Revisi :
SATUAN ACARA PERKULIAHAN Fakultas/ Jurusan/ Program Studi Kode Matakuliah Nama Matakuliah Kelompok Matakuliah Semester/SKS Pertemu an ke1
Tujuan Instruksional Umum Memahami Konsep dasar dan Model Bahasa dan Automata.
Tujuan Instruksional Khusus Memahami model-model komputasi sebagai mesin abstraks yang dapat didefinisikan secara matematis, mulai dari yang paling sederhana hingga yang paling powerful.
: : : : :
Teknologi Industri/ Teknik Informatika/ Teknik Informatika 52302031 Teori Bahasa dan Automata MPK/MKK/MKB/MBB/Praktikum IV/3
Pokok Bahasan Konsep dasar Model Bahasa dan Automata.
Materi Model-model sederhana formalisasi matematis yang terbentuk secara bertahap, hubungan dengan situasisituasi dunia nyata (masalahmasalah modelmodel komputasi sedehana).
Media White board, PC Viewer
Metode tatap muka, tanya jawab
Evaluasi Latihan, PR
Sumber/ Referensi A,B,C,D
Pertemu an ke2
Tujuan Instruksional Umum Memahami konsep Bahasa-bahasa Regular,Ekspresi Regular.
Tujuan Instruksional Khusus Mengetahui Bahasa Regular dihasilkan dari bahasa sederhana dengan melakukan operasi-operasi gabungan, konkatenasi, dan/atau Kleene-*.
Pokok Bahasan Bahasa-bahasa Regular,Ekspre si Regular Tor.
3
Memahami konsep Finite Automata, Operasi Himpunan pada Bahasa Regular.
Mengetahui Finite Automaton (FA) atau Finite State Automaton (FSA).
Finite Automata, Operasi Himpunan pada Bahasa Regular.
4
Memahami konsep NFA, Konversi NFA ke FA, NFA-Lambda, Konversi NFA-Lambda ke NFA.
Mengetahui karakteristik FA dari suatu bahasa regular Mengetahui kelas-kelas FA yang memiliki sifat-sifat khusus tertentu.
NFA, Konversi NFA ke FA, NFA-Lambda, Konversi NFALambda ke NFA.
5
Memahami Teorema Kleene, Minimisasi FA.
Mengetahui konsep nondeterministisme dari suatu ekspresi regular
Teorema Kleene, Minimisasi FA.
Materi
Media
Metode
Evaluasi
Sumber/ Referensi A,B,C,D
Ekspresi Regular, Definisi Formal Ekspresi Reguler, Hirarki antar operator, dan Aljabar Ekspresi Reguler.
White board, PC Viewer
tatap muka, tanya jawab
Latihan, PR
Definisi FA, Perluasan fungsi transisi menjadi *, FA Sebagai Recognizer dari Bahasa Regular, danOperasiOperasi Himpunan. Definisi NFA, Fungsi Perluasan Transisi *, NFA sebagai mesin pengenal bahasa reguler, danTeorema konversi NFA ke FA. Transisi Definisi NFA
White board, PC Viewer
tatap muka, tanya jawab
Latihan, PR
A,B,C,D
White board, PC Viewer
tatap muka, tanya jawab
Latihan, PR
A,B,C,D
White board, PC
tatap muka, tanya
Latihan, PR
A,B,C,D
Pertemu an ke-
6
Tujuan Instruksional Umum
Memahami Pumping Lemma, Sifat-sifat Bahasa Regular
Tujuan Instruksional Khusus suatu NFA yang dapat menerima bahasa. Mengetahui kasus-kasus dimana nondeterminisme tidak dapat dilakukan secara sederhana.
Mengetahui suatu bahasa reguler dapat langsung diperoleh dengan transisi ^. Mengetahui bahwa bahasa reguler dapat dipandang sebagai hasil operasi penggabungan, konkatenasi dan kleene dari bahasa-bahasa paling sederhana dari alfabetnya.
Pokok Bahasan
Materi
Fungsi Perluasan Transisi , closure dari Himpunan Status, Algoritma Pencarian (S), Definisi * untuk NFA , Kompatibilitas NFA dengan NFA, Menentukan 1 dari . Pumping Minimalisasi Lemma, Sifat- String, sifat Bahasa keberadaan Regular string, Relasi ekivalensi tak terbedakan, Partisi Kelas Ekivalensi,
Media
Metode
Viewer
jawab
White board, PC Viewer
tatap muka, tanya jawab
Evaluasi
Latihan, PR
Sumber/ Referensi
A,B,C,D
Pertemu an ke7
Tujuan Instruksional Umum Memahami Grammar dan Bahasa Bebas Konteks
Tujuan Instruksional Khusus Mengetahui penurunan bahasa dengan grammar reguler dan penggunaan parse tree. mengetahui aplikasi dari grammar bebas konteks. Memahami ambigu pada bahasa dan grammar
Pokok Bahasan GrammarBebas Konteks (CFG) dan Bahasa Bebas Konteks (CFL)
8
Memahami Pushdown Automata
Pushdown Automata (PDA)
9
Memahami Properti dari Bahasa Bebas Konteks
Mengetahui Pushdown Automata, proses penurunan bahasa dengan PDA, ekuivalensi PDA dan CFG, PDA Deterministik Mengetahui bentuk normal dari CFG, Pumping Lemma untuk CFL, Properti Closure dari CFL, Properti Keputusan dari CFL
10
Memahami Properti dari Bahasa Bebas Konteks
Mengetahui normal dari
Bentuk Normal CFG
bentuk Chomsky CFG, Normal Form
Materi
Media
Metode
Evaluasi
Sumber/ Referensi A,B,C,D
Definisi CFG, Definisi CFL, Operasi-operasi gabungan, konkatenase dan kleene pada CFL, Pohon Penurunan, Ambiguitas pada CFG Definisi PDA, Bahasa PDA, Ekuivalensi PDA dan CFG, PDA Deterministik
White board, PC Viewer
tatap muka, tanya jawab
Latihan, PR
White board, PC Viewer
tatap muka, tanya jawab
Latihan, PR
A,B,C,D
Eliminasi useless symbols, Komputasi generating & reachable symbols, Eliminasi epsilonproduction, Eliminasi Unitproduction, Chomsky Normal Form Menghilangkan produksi ,
White board, PC Viewer
tatap muka, tanya jawab
Latihan, PR
A,B,C,D
White board,
tatap muka,
Latihan, PR
A,B,C,D
Pertemu an ke-
Tujuan Instruksional Umum
Tujuan Instruksional Pokok Khusus Bahasan Pumping Lemma untuk CFL, Properti Closure dari CFL, Properti Keputusan dari CFL Mengetahui Mesin-mesin Thesis Churchabstraks yang telah Turing, TM, dipelajari merupakan Kombinasi TM model algoritmaalgoritma (model komputasi) untuk kelas-kelas masalah tertentu dengan string masukan masukan dapat memberikan jawaban “ya” atau “tidak”.
Materi
Media
Metode
Evaluasi
Sumber/ Referensi
Menghilangkan PC produksi unit, Viewer Bentuk CNF,
tanya jawab
Model komputasi, Model mesin turing, Kombinasi Mesin turing, dan komputasi mesin parsial.
White board, PC Viewer
tatap muka, tanya jawab
Latihan, PR
A,B,C,D
11
Memahami Properti dari Bahasa Bebas Konteks
12
Memahami Properti dari Bahasa Bebas Konteks
Mengetahui varian TM yang menggunakan lebih dari satu tape. Mengetahui kemampuan TM multitape.
TM Multitape, NTM, UTM
Mesin turing multitape, Mesin turing nondeterministik, Mesin turing universal
White board, PC Viewer
tatap muka, tanya jawab
Latihan, PR
A,B,C,D
13
Memahami Properti dari Bahasa Bebas Konteks
Mengetahui bahwa tidak semua bahasa RE adalah rekursif.
Bahasa-bahasa Rekursif dan Rekursively Enumerable, Bahasa NonRE
Bahasa-bahasa non RE.Unrestricted grammar, Grammar dan bahasa context sensitive, dan
White board, PC Viewer
tatap muka, tanya jawab
Latihan, PR
A,B,C,D
Pertemu an ke14
Tujuan Instruksional Umum Memahami Unsolvable Problem dan Solveable Problem
Tujuan Instruksional Khusus Mengetahui konsep masalah-masalah yang tidak bisa dipecahkan dengan automata. Mengetahui konsep masalah-masalah yang bisa dipecahkan dengan automata.
Pokok Bahasan Unsolvable Problem dan Solveable Problem
Materi Hirarky Chomsky Perkembangan automata. Perkembangan permasalahan yang bisa dipecahkan dengan automata.Perkem bangan masalahmasalah yang tidak bisa dipecahkan dengan automata.
Media
White board, PC Viewer
Metode
tatap muka, tanya jawab
Evaluasi
Latihan, PR
Sumber/ Referensi A,B,C,D
Sumber/Referensi : A. Hopcroft, John. E, dan Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation, USA : Addison Wesley, 1979.. B. Linz, Peter, Automata and Formal Language, DC, 1990. C. Narendra, Kumara, Learning Automata an Introduction, Prentice Hall, 1989. D. Reverz, G., Introduction to Formal Language and Automaya, New York : McGraw-Hill, 1985.
Disahkan oleh Dekan Fakultas Teknologi Industri
Disiapkan oleh Ketua Jurusan Teknik Informatika
Fathul Wahid, ST., M.Sc.
Yudi Prayudi, S.Si., M. Kom.
