SOAL UJIAN AKHIR SEMESTER (UAS)
TEORI BAHASA DAN OTOMATA
FAKULTAS TEKNIK
UNIVERSITAS ISLAM MADURA
TEORI BAHASA DAN OTOMATA
FAKULTAS TEKNIK
UNIVERSITAS ISLAM MADURA
| Nama : Hamdani | |
| Npm : 2016020100014 |
KETENTUAN:
1. Wajib Mengisi Identitas Nama dan NPM
2. Jawaban langsung ditulis pada Halaman File ini.
3. Sifat Ujian Open Soure (Sumber Terbuka) dari Buku, E-Book, Internet, Kecuali Open Teman
(Dilarang Menyontek). Sertakan Nama Sumber (Misalnya Judul Buku atau Alamat Situs)
dimasing-masing Jawaban.
4. File disimpan dalam format Portable Document Format (PDF).
5. File diberi Nama File dengan Format NPM_Nama, misalnya: 2016020100014_sanysolution.pdf
6. File jawaban dikirim ke hamdanibcr@gmail.com, paling lambat jam 21.00 WIB.
SOAL
1. Sebutkan pengertian automata dan sifat-sifatnya
2. Jelaskan pengertian tentang Diagram Transisi dan Expressi Regular! Berikan contohnya !
3. Sebutkan definisi formal Deterministic dan Non Deterministic State Automata!
4. Jelaskan proses kerja dari Finite State Autmata !
5. Bagaimana mengubah fungsi transisi menjadi untai atau disebut juga dengan extended
transition function(fungsi transisi yang diperluas) pada DFA?
6. Sebutkan perbedaan antara DFA dengan NFA, yang mudah dikenali !
7. Jelaskan tentang perluasan fungsi transisi pada NFA!
8. Jelaskan apa yang disebut dengan Ekwivalensi DFA dan NFA!
9. Sebutkan 4 komponen penting dalam grammer (Tatabahasa) suatu bahasa !
10. Apa yang dimaksud -move dan -closure?
11. Tentukan semua string yang dapat dibangkitkan dari ekspresi L((a+b)*b(a+ab)*) dengan
panjang string kurang dari 4 karakter
12. Jelaskan mengapa final state dari mesin moore dan mealy dihilangkan? Berikan
analisamu!
13. Buatlah DFA yang ekuivalen dengan NFA dibawah ini!
14. Transformasikan CFG kedalam bentuk normal Chomsky: S → aSb | ab
15. Transformasikan kedalam bentuk normal Chomsky:
S → AA | C | bd
A → Bb
B → B | AB | d
C → de
Lakukan penyederhanaan terlibh dahulu bila perlu
16. Apa tujuan penyederhanaan CFG? Dan ada berapa 3 cara?
Diketahui grammar G(V, V, S, P) dimana :
V = {a, b}
V = {S, A, B}
S ε Vn
P = {S –> aA; A–> aB| b; B–> bS; }
▪ G termasuk grammar tipe berapa? Berikan alasannya.
▪ Buatlah 5 kalimat dengan panjang berbeda yang dapat diturunkan dari grammar G.
▪ Tentukan bahasa dari grammar G ( L(G)).
1. Wajib Mengisi Identitas Nama dan NPM
2. Jawaban langsung ditulis pada Halaman File ini.
3. Sifat Ujian Open Soure (Sumber Terbuka) dari Buku, E-Book, Internet, Kecuali Open Teman
(Dilarang Menyontek). Sertakan Nama Sumber (Misalnya Judul Buku atau Alamat Situs)
dimasing-masing Jawaban.
4. File disimpan dalam format Portable Document Format (PDF).
5. File diberi Nama File dengan Format NPM_Nama, misalnya: 2016020100014_sanysolution.pdf
6. File jawaban dikirim ke hamdanibcr@gmail.com, paling lambat jam 21.00 WIB.
SOAL
1. Sebutkan pengertian automata dan sifat-sifatnya
2. Jelaskan pengertian tentang Diagram Transisi dan Expressi Regular! Berikan contohnya !
3. Sebutkan definisi formal Deterministic dan Non Deterministic State Automata!
4. Jelaskan proses kerja dari Finite State Autmata !
5. Bagaimana mengubah fungsi transisi menjadi untai atau disebut juga dengan extended
transition function(fungsi transisi yang diperluas) pada DFA?
6. Sebutkan perbedaan antara DFA dengan NFA, yang mudah dikenali !
7. Jelaskan tentang perluasan fungsi transisi pada NFA!
8. Jelaskan apa yang disebut dengan Ekwivalensi DFA dan NFA!
9. Sebutkan 4 komponen penting dalam grammer (Tatabahasa) suatu bahasa !
10. Apa yang dimaksud -move dan -closure?
11. Tentukan semua string yang dapat dibangkitkan dari ekspresi L((a+b)*b(a+ab)*) dengan
panjang string kurang dari 4 karakter
12. Jelaskan mengapa final state dari mesin moore dan mealy dihilangkan? Berikan
analisamu!
13. Buatlah DFA yang ekuivalen dengan NFA dibawah ini!
14. Transformasikan CFG kedalam bentuk normal Chomsky: S → aSb | ab
15. Transformasikan kedalam bentuk normal Chomsky:
S → AA | C | bd
A → Bb
B → B | AB | d
C → de
Lakukan penyederhanaan terlibh dahulu bila perlu
16. Apa tujuan penyederhanaan CFG? Dan ada berapa 3 cara?
Diketahui grammar G(V, V, S, P) dimana :
V = {a, b}
V = {S, A, B}
S ε Vn
P = {S –> aA; A–> aB| b; B–> bS; }
▪ G termasuk grammar tipe berapa? Berikan alasannya.
▪ Buatlah 5 kalimat dengan panjang berbeda yang dapat diturunkan dari grammar G.
▪ Tentukan bahasa dari grammar G ( L(G)).
0 Response to "CONTOH SOAL TEORI BAHASA DAN OTOMATA FAKULTAS TEKNIK"
Post a Comment