silabus a. identitas matakuliahti.ft.unmuhjember.ac.id/images/kurikulum/22-teori-bahasa-dan...6 nfa...
Post on 08-Apr-2019
312 Views
Preview:
TRANSCRIPT
SILABUS
A. IDENTITAS MATAKULIAH Program Studi Teknik Informatika
Nama Matakuliah (MK) Teori Bahasa dan Automata Direvisi:
Kode/Bobot MK MJU.TIK-010/ 3 SKS
Semester 4
MK Prasyarat (jika ada) -
Pengampu 1. Ginanjar Abdurrahman, S.Si, M.Pd
CAPAIAN PEMBELAJARAN (CP)
No Capaian Pembelajaran Program Studi
Capaian Pembelajaran MK
1. Bertakwa kepada Tuhan Yang Maha Esa
Memahami konsep dan teori dasar automata, bahasa, komputabilitas dan kompleksitasuntuk membentuk dasar dari penalaran formal komputer dan menjelaskan keterbatasan komputabilitas serta memberikan definisi yang jelas dan formal untuk masalah komputasi dan algoritma.
2. Memiliki moral, etika dan kepribadian yang baik di dalam menyelesaikan tugas
3. Berperan sebagai warga Negara yang bangga dan cinta tanah air serta mendukung perdamaian dunia
4. Mampu bekerja sama dan memiliki kepekaan sosial dan kepedulian yang tinggi terhadap masyarakat dan lingkungannya
5. Menghargai keanekaragaman budaya, pandangan, kepercayaan, dan agama serta pendapat/temuan original orang lain
6. Menjunjung tinggi penegakan hukum serta memiliki semangat untuk mendahulukan kepentingan bangsa serta masyarakat luas.
DESKRIPSI MATAKULIAH: Mata kuliah ini bertujuan untuk memberikan bekal pengetahuan mengenai latar belakang perancangan bahasa pemrograman dan memberikan kemampuan memodelkan permasalahan nyata menggunakan automata sebagai alat pemodelannya (dengan studi kasus bahasa pemrograman). Selain itu, mahasiswa diharapkan dapat mengasah kemamuan mendefinisikan objek atau himpunan tertentu dengan menggunakan definisi rekursif, baik secara mandiri atau juga dalam kerjasama tim.
7. Mampu mengaplikasikan bidang keahliannya dan memanfaatkan ilmu pengetahuan, teknologi, dan/atau seni pada bidangnya dalam penyelesaian masalah serta mampu beradaptasi terhadap situasi yang dihadapi
algoritma.
8. Menguasai konsep teoritis bidang pengetahuan tertentu secara umum dan konsep teoritis bagian khusus dalam bidang pengetahuan tersebut secara mendalam, serta mampu memformulasikan penyelesaian masalah prosedural.
ANALISIS INSTRUKSIONAL
Mata Kuliah : Teori Bahasa dan Automata
Ruang Lingkup Mata Kuliah Teori Bahasa dan Automata
Teori Dasar Bahasa dan Automata
Finite State Automata (FSA)
Deterministik Finite Automata (DFA)
EkuivalensiNFA⬄ DFA
NFA ( Non-Deterministik Finite Automata
Finite Automata dan Ekspresi Reguler
Ekspresi Reguler (ER)
Context Free Grammar (CFG)
Sifat-sifat Bahasa Reguler
Parse Tree
Ekuivalensi PDA dan CFG
Pushdown Automata (PDA)
Aplikasi CFG
Memahami konsep dan teori dasar automata, bahasa, komputabilitas dan kompleksitasuntuk membentuk dasar dari penalaran formal komputer dan menjelaskan keterbatasan komputabilitas serta memberikan definisi yang jelas dan formal untuk masalah komputasi dan algoritma.
KOMPETENSI AKHIR YANG DIRENCANAKAN (KAD)
Capaian Pembelajaran MK
:
Kompetensi yang Diharapkan
No. KAD
Rumusan KAD
1 Ruang Lingkup Mata Kuliah Teori Bahasa dan Automata
2 Teori Dasar Bahasa dan Automata
3 Finite State Automata (FSA)
4 Deterministic Finite Automata (DFA)
5 Non-Deterministic Finite Automata (NDFA)
6 NFA (Non-Deterministic Finite Automata) ⬄ DFA (Deterministic Finite Automata)
7 Ekspresi Reguler
8 Finite Automata dan Ekspresi Reguler
9 Sifat-sifat Bahasa Reguler
10 Context Free Grammars (CFG)
11 Parse Trees
12 Aplikasi CFG
13 Pushdown Automata (PDA)
14 Ekuivalensi PDA dan CFG
E. Contoh Format RENCANA PEMBELAJARAN SEMESTER
Sistem Perkuliahan a. Pendekatan b. Model c. Metode/Strategi
: ........................... : ........................... : ...........................
Media Pembelajaran : Laptop, LCD Proyektor, Slide Powerpoint
Penilaian ! Presensi/Kehadiran (P) ! Tugas (T) ! UTS (UT) ! UAS (UA)
: 10 % : 30 % : 30 % : 30 %
NILAI AKHIR= 10P+30T+30UTS+30UAS : 100
Pustaka 1. Introduction to the theory of Automata Theory, Languages, and computation, 3rd edition, John Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. cencage learning, 2013
2. Automata, Computability, and Complexity, Theory and Application, Pearson International Edition, 2009.
Minggu Kemampuan Akhir yang
Materi Pembelajaran
Bentuk dan Metode
Alokasi Pengalaman
Belajar Kriteria Capaian Penilaian
Minggu Ke-
Akhir yang Direncanakan
(KAD)
Materi Pembelajaran
(Materi Pokok)
Bentuk dan Metode
Pembelajaran
Alokasi Waktu
Belajar Kriteria Capaian (Indikator) Bentuk Bobot
(1) (2) (3) (4) (5) (6) (7) (8) (9)
1 Membahas Silabus, Kontrak Perkuliahan, dan Ruang lingkup perkuliahan Teori Bahasa dan Automata
1. Silabus 2. Kontrak
Perkuliahan 3. Pengantar
Perkuliahan Teori Bahasa dan Automata
Presentasi 3 x 50 ‘ P r e s e n t a s i t e n t a n g S i l a b u s , k o n t r a k perkuliahan, d a n P e n g a n t a r Perkuliahan Teori Bahasa d a n Automata
1. M a h a s i s w a d a p a t m e m a h a m i s i l a b u s d a n k o n t r a k perkuliahan (C2)
2. M a h a s i s w a d a p a t m e m a h a m i p e n g a n t a r p e r k u l i a h a n Teor i Bahasa dan Automata (C2)
Presentasi dan Diskusi
20 %
2 Teori Dasar Bahasa dan Automata
1. Definisi Automata
2. Pernyataan If-Then
3. Pernyataan If and only if
4. Teorema yang terlihat bukan If-Then statemen
5. Pembuktian dengan Kontrapositif
6. Pembuktian dengan Kontradiksi
7. Pembuktian dengan Counterexamples
8. Alfabet 9. String 10.Alfabet dan
String 11. Konkatenasi
dari string 12.Terminologi
Bahasa 13.Operasi-
Presentasi dan diskusi
3 x 50 ‘ P r e s e n t a s i dan diskusi m e m b a h a s tentang Teori dasar bahasa dan automata
1. M a h a s i s w a d a p a t m e n j e l a s k a n d e f i n i s i automata (C2)
2. M a h a s i s w a d a p a t m e n e n t u k a n nilai kebenaran statemen if-then (C3)
3. M a h a s i s w a d a p a t m e n e n t u k a n nilai kebenaran pernyataan i f and only if (C3)
4. M a h a s i s w a d a p a t mengidentifikasi teorema yang terlihat bukan pernyataan if-then (C1)
5. M a h a s i s w a d a p a t m e n e r a p k a n p e m b u k t i a n d e n g a n k o n t r a p o s i t i f
Presentasi dan Diskusi
20 %
3 Finite State Automata (FSA)
1. Definisi FSA 2. Macam-
macam FSA: DFA dan NFA
3. Gambaran informal finite automata, studi kasus: uang elektronik
4. Seluruh sistem sebagai automaton
5. Penggunaan produk automaton untuk validasi protocol
Presentasi dan diskusi
3 x 50 ‘ P r e s e n t a s i dan diskusi m e m b a h a s t e n t a n g Finite State A u t o m a t a (FSA)
1. Mahasiswa dapat menjelaskan Definisi FSA (C2)
2. Mahasiswa dapat menyebutkan macam-macam FSA: DFA dan NFA (C1)
3. Mahasiswa dapat menjelaskan gambaran informal finite automata, studi kasus: uang elektronik (C2)
4. Mahasiswa dapat memahami seluruh sistem sebagai automaton (C2)
5. Mahasiswa dapat menjelaskan penggunaan produk automaton untuk validasi protocol (C2)
Presentasi dan Diskusi
20 %
4 Deterministik Finite Automata (DFA)
1. Definisi DFA 2. Cara DFA
memproses string
3. Initial state DFA
4. Final state DFA
5. Diagram transisi DFA
6. Tabel transisi DFA
7. Fungsi transisi untuk memproses input dengan DFA
8. Penerimaan/Penolakan oleh DFA
Presentasi dan diskusi
3 x 50 ‘ P r e s e n t a s i dan diskusi m e m b a h a s t e n t a n g Deterministik F i n i t e A u t o m a t a (DFA)
1. M a h a s i s w a d a p a t m e n j e l a s k a n d e f i n i s i D FA (C2)
2. M a h a s i s w a d a p a t m e n j e l a s k a n c a r a D F A m e m p r o s e s string (C2)
3. M a h a s i s w a d a p a t m e m a h a m i initial state DFA (C2)
4. M a h a s i s w a d a p a t memahami Final State DFA (C2)
5. M a h a s i s w a d a p a t m e n j e l a s k a n diagram transisi DFA (C2)
6. M a h a s i s w a d a p a t m e n j e l a s k a n tab le t rans is i DFA (C2)
Presentasi dan Diskusi
20 %
5 NFA ( Non-Deterministik Finite Automata
1. Definisi NFA 2. Cara NFA
memproses string
3. Initial state NFA
4. Final state NFA
5. Diagram transisi NFA
6. Tabel transisi NFA
7. Fungsi transisi untuk memproses input dengan NFA
8. Penerimaan/Penolakan oleh NFA
Presentasi dan diskusi
3 x 50 ‘ P r e s e n t a s i dan diskusi m e m b a h a s tentang NFA ( N o n -Deterministik F i n i t e Automata
1. M a h a s i s w a d a p a t m e n j e l a s k a n d e f i n i s i N FA (C2)
2. M a h a s i s w a d a p a t m e n j e l a s k a n c a r a N F A m e m p r o s e s string (C2)
3. M a h a s i s w a d a p a t m e m a h a m i initial state NFA (C2)
4. M a h a s i s w a d a p a t memahami Final State NFA (C2)
5. M a h a s i s w a d a p a t m e n j e l a s k a n diagram transisi NFA (C2)
6. M a h a s i s w a d a p a t m e n j e l a s k a n tab le t rans is i NFA (C2)
Presentasi dan Diskusi
20 %
6 Ekuivalensi NFA⬄ DFA
1. Definisi ekuivalensi NFA⬄ DFA
2. Konversi DFA=>NFA
3. Konversi NFA=>DFA
Presentasi dan diskusi
3 x 50 ‘ P r e s e n t a s i dan diskusi m e m b a h a s t e n t a n g Ekuivalensi NFA⬄ DFA
1. Mahasiswa dapat m e m a h a m i d e f i n i s i e k u i v a l e n s i NFA⬄ DFA (C2)
2. Mahasiswa dapat m e n e n t u k a n k o n v e r s i DFA=>NFA (C3)
3. Mahasiswa dapat m e n e n t u k a n k o n v e r s i NFA=>DFA (C3)
Presentasi dan Diskusi
20 %
7 Ekspresi Reguler (ER)
1. Definisi Ekspresi Reguler (ER)
2. Operator dalam Ekspresi Reguler
3. Menyusun Ekspresi Reguler
4. Operator yang didahulukan dalam ekspresi regular
5. Aplikasi Ekspresi Reguler pada UNIX
6. Aplikasi Ekspresi Reguler pada Analisis Leksikal
7. Aplikasi Ekspresi Reguler pada pencarian pola dalam
Presentasi dan diskusi
3 x 50 ‘ P r e s e n t a s i dan diskusi m e m b a h a s t e n t a n g E k s p r e s i Reguler (ER)
1. Mahasiswa dapat m e n j e l a s k a n definisi ekspresi regular (C2)
2. Mahasiswa dapat m e n j e l a s k a n operator dalam ekspresi regular (C2)
3. Mahasiswa dapat m e n y u s u n ekspresi regular (C6)
4. Mahasiswa dapat m e n e r a p k a n operator yang d i d a h u l u k a n dalam ekspresi regular (C3)
5. Mahasiswa dapat m e n j e l a s k a n aplikasi ekspresi r e g u l a r p a d a UNIX
6. Mahasiswa dapat m e n j e l a s k a n aplikasi ekspresi r e g u l a r p a d a Analisis Leksikal
7. Mahasiswa dapat
Presentasi dan Diskusi
20 %
8 Finite Automata dan Ekspresi Reguler
1. Hubungan Finite Automata dengan Ekspresi Reguler
2. Konversi DFA=> Ekspresi Reguler
3. Konversi DFA => Ekspresi Reguler dengan mengeliminasi state
4. Konversi Ekspresi Reguler=> Automata
5. Aturan-aturan aljabar pada Ekspresi Reguler
Presentasi dan diskusi
3 x 50 ‘ P r e s e n t a s i dan diskusi m e m b a h a s t e n t a n g F i n i t e A u t o m a t a dan Ekspresi Reguler
1. Mahasiswa dapat m e n j e l a s k a n hubungan finite automata dengan ekspresi regular (C2)
2. Mahasiswa dapat m e n e n t u k a n k o n v e r s i DFA=>Ekspresi Reguler (C3)
3. Mahasiswa dapat m e n e n t u k a n k o n v e r s i DFA=>Ekspresi Reguler dengan mengeliminasi state (C3)
4. Mahasiswa dapat m e n e n t u k a n k o n v e r s i E k s p r e s i R e g u l e r = > Automata (C3)
5. Mahasiswa dapat m e n j e l a s k a n a t u r a n - a t u r a n a l j a b a r p a d a ekspresi regular ( A s o s i a t i f ,
Presentasi dan Diskusi
20 %
9 Sifat-sifat Bahasa Reguler
1. Pembuktian bahasa bukan bahasa regular
2. Sifat-sifat closure dalam bahasa regular
3. Closure dari bahasa regular dalam bentuk operasi Boolean
4. Reversal 5. Homomorphi
sms 6. Inverse
homomorphisms
1. Mahasiswa dapat m e n j e l a s k a n p e m b u k t i a n bahasa bukan regular
2. Mahasiswa dapat m e n j e l s a k a n sifat-sifat closure da lam bahasa regular (C2)
3. Mahasiswa dapat m e n j e l a s k a n c l o s u r e d a r i bahasa regular da lam ben tuk operasi Boolean (C2)
4. Mahasiswa dapat m e n j e l a s k a n reversal (C2)
5. Mahasiswa dapat m e n j e l a s k a n homomorphisms (C2)
6. Mahasiswa dapat m e n j e l a s k a n i n v e r s e homomorphisms (C2)
10 Context Free Grammar (CFG)
1. Definisi CFG
2. Derivasi menggunakan grammar
3. Derivasi leftmost
4. Derivasi rightmost
5. Bahasa grammar
6. Bentuk-bentuk Sentential
Presentasi dan diskusi
3 x 50 ‘ P r e s e n t a s i dan diskusi m e m b a h a s t e n t a n g Context Free G r a m m a r (CFG)
1. Mahasiswa dapat m e n j e l a s k a n d e f i n i s i C F G (C2)
2. Mahasiswa dapat m e n e n t u k a n derivasi leftmost (C3)
3. Mahasiswa dapat m e n e n t u k a n d e r i v a s i rightmost (C3)
4. Mahasiswa dapat m e n j e l a s k a n bahasa grammar (C2)
5. Mahasiswa dapat m e n j e l a s k a n bentuk-bentuk sentential (C2)
Presentasi dan Diskusi
20 %
11 Parse Tree 1. Definisi Parse Trees
2. Mengkonstruksi Parse Tree
3. Hasil dari Parse Tree
4. Inferensi, Derivasi, dan Parse Tree
Presentasi dan diskusi
3 x 50 ‘ P r e s e n t a s i dan diskusi m e m b a h a s tentang Parse Tree
1. Mahasiswa dapat m e n j e l a s k a n def inis i parse tree (C2)
2. Mahasiswa dapat mengkonstruksi parse tree (C6)
3. Mahasiswa dapat m e n e n t u k a n hasil dari parse tree (C3)
4. Mahasiswa dapat m e n j e l a s k a n i n f e r e n s i , d e r i v a s i d a n parse tree (C2)
Presentasi dan Diskusi
20 %
12 Aplikasi CFG 1. Parsers 2. YACC
Parser-Generator
3. Markup Languages
4. XML dan Document-Type Definition (DTD)
5. Ambiguitas Grammar
6. Menghilangkan Ambiguitas dari Grammar
7. Derivasi Leftmost sebagai cara untuk memperlihatkan ambiguitas
8. Ambiguitas yang melekat
Presentasi dan diskusi
3 x 50 ‘ P r e s e n t a s i dan diskusi m e m b a h a s tentang
1. Mahasiswa dapat menjelaskan Parsers (C2)
2. Mahasiswa dapat menjelaskan YACC Parser-Generator (C2)
3. Mahasiswa dapat menjelaskan Markup Languages (C2)
4. Mahasiswa dapat menjelaskan XML dan Document-Type Definition (DTD) (C2)
5. Mahasiswa dapat menjelaskan Ambiguitas Grammar
6. Mahasiswa dapat menjelaskan Cara Menghilangkan Ambiguitas dari Grammar (C2)
7. Mahasiswa dapat menjelaskan
Presentasi dan Diskusi
20 %
13 Pushdown Automata (PDA)
1. D e f i n i s i PDA
2. Transisi PDA 3. Notasi grafis
untuk PDA 4. Instantaneou
s Desctiption dari PDA
5. Bahasa PDA 6. Penerimaan
o leh F ina l State
7. Penerimaan oleh Stack kosong
8. Dar i s tack k o s o n g k e final state
9. D a r i f i n a l state ke stack kosong
Presentasi dan diskusi
3 x 50 ‘ P r e s e n t a s i dan diskusi m e m b a h a s t e n t a n g P u s h d o w n A u t o m a t a (PDA)
1. Mahasiswa dapat m e n j e l a s k a n d e f i n i s i P D A (C2)
2. Mahasiswa dapat m e n e r a p k a n Trans i s i PDA (C2)
3. Mahasiswa dapat m e n j e l a s k a n N o t a s i g r a f i s untuk PDA (C2)
4. Mahasiswa dapat m e n e r a p k a n I n s t a n t a n e o u s Description dari PDA (C2)
5. Mahasiswa dapat m e m a h a m i B a h a s a P D A (C2)
6. Mahasiswa dapat m e j e l a s k a n penerimaan oleh final state (C2)
7. Mahasiswa dapat m e n j e l a s k a n penerimaan oleh s t a c k k o s o n g (C2)
Presentasi dan Diskusi
20 %
14 Ekuivalensi PDA dan CFG
1. Kesetaraan kelas bahasa PDA dan CFG
2. Konversi CFG=>PDA
3. Konversi PDA=>CFG
4. Deterministic PDA
Presentasi dan diskusi
3 x 50 ‘ P r e s e n t a s i dan diskusi m e m b a h a s t e n t a n g Ekuivalensi P D A d a n CFG
1. Mahasiswa dapat menjelaskan kesetaraan kelas bahasa PDA dan CFG (C2)
2. Mahasiswa dapat menentukan Konversi CFG=>PDA (C3)
3. Mahasiswa dapat menentukan Konversi PDA=>CFG (C3)
4. Mahasiswa dapat menjelaskan definisi Deterministic PDA (C2)
Presentasi dan Diskusi
20 %
Jember, .................................. Dosen Pengampu,
GINANJAR ABDURRAHMAN, S.Si, M.Pd NIDN. 0714078704
top related