Tugas Besar Teori Komputasi 2010

Definisi dan mekanisme tugas besar

1. Mahasiswa akan mengerjakan dalam 1 kelompok dengan maksimum jumlah anggota adalah 4.
2. Masing-masing kelompok diminta memilih satu dari beberapa topik yang akan diimplementasikan.
3. Semua topik harus diambil oleh semua kelompok di kelas secara merata. Jadi tidak boleh ada topik yang tidak diambil. (bisa difasilitasi dosen atau ketua kelas)
4. Setiap topik harus dibuatkan programnya dalam bahasa Java.
5. Waktu pengumpulan adalah minggu terakhir sebelum UAS (Hari Jum’at).
6. File yang harus dikumpulkan adalah :
a. Source Code dan jar dari program
b. File dependensi yang dibutuhkan (library dan versi java yang dipergunakan)
c. Contoh file input setidaknya 4 contoh yang bisa dilakukan konversi.
7. Pilihan topik yang bisa diimplementasikan adalah sebagai berikut :
a. State Transition Diagram ke Program Terjemahan
b. Non Deterministik Finite Automata ke Determnistik Finite Automata
c. Non Deterministik Finite Automata e-Move ke Determnistik Finite Automata
d. DFA ke Minimum DFA
e. DFA Notasi Formal ke DFA bentuk state transition diagram
f. Context Free Grammer ke Push Down Automata
g. Push Down Automata ke Context Free Grammer
h. Context Free Grammer ke CNF
8. Masing-masing topik harus dibuat dinamis sehingga memungkinkan input yang lain bisa dipergunakan / dikonversi
9. Penjelasan masing-masing topik adalah sebagai berikut
a. State Transition Diagram ke Program Terjemahan
State transition diagram yang menjadi masukan adalah state transition diagram notasi bahasa formal dalam (Q, å, d,q1,F) dengan Q adalah himpunan state, å adalah himpunan alfabet, d adalah aturan transisi,q1 adalah aturantransisi,F adalah himpunan final state.
Contoh



b. Non Deterministik Finite Automata ke Determnistik Finite Automata
Non Deterministik Finite Automata yang menjadi masukan adalah state transition diagram notasi bahasa formal dalam A = (Q, å, d,q1,F) dengan Q adalah himpunan state, å adalah himpunan alfabet, d adalah aturan transisi,q1 adalah aturantransisi,F adalah himpunan final state.
Dan deterministic finite automata yang dihasilkan juga dalam notasi formal
c. Non Deterministik Finite Automata e-Move ke Determnistik Finite Automata
Non Deterministik Finite Automata e-Move yang menjadi masukan adalah state transition diagram notasi bahasa formal dalam A = (Q, å, d,q1,F) dengan Q adalah himpunan state, å adalah himpunan alfabet, d adalah aturan transisi,q1 adalah aturantransisi,F adalah himpunan final state.
Dan deterministic finite automata yang dihasilkan juga dalam notasi formal

d. DFA ke Minimum DFA
Dari notasi formal ke notasi formal
e. DFA Notasi Formal ke DFA bentuk state transition diagram
jelas
f. Context Free Grammer ke Push Down Automata
jelas
g. Push Down Automata ke Context Free Grammer
jelas
h. Context Free Grammer ke CNF
Ditunjukkan per langkah mulai dari Mengeliminasi produksi ε, Mengeliminasi produksi unit (bentuk A B), dan Mengeliminasi useless symbol, hingga hasil akhir CNFnya