Pertemuan 6
Non Deterministic Finite Automata (NFA) / Automata Non Deterministik
Pretest
- Apa perbedaan DFA dan NFA pada transisi?
- Dalam NFA, apakah satu state boleh punya lebih dari satu transisi untuk simbol yang sama?
- Kapan string dianggap diterima oleh NFA?
Modul (Ringkasan Materi)
NFA adalah automata hingga yang memperbolehkan lebih dari satu transisi untuk suatu simbol, bahkan bisa tidak memiliki transisi untuk simbol tertentu.
- NFA dapat “memilih” jalur transisi (non-deterministic).
- String diterima jika ada minimal satu jalur yang berakhir di state accepting.
- Secara konsep, proses NFA bisa dilihat sebagai himpunan state aktif setelah membaca tiap simbol.
Posttest
- Jelaskan accept/reject pada NFA (kata kunci: “ada jalur”).
- Apakah NFA dan DFA sama kuat untuk bahasa regular?
- Sebutkan 1 alasan NFA sering lebih mudah didesain.
Tugas
- Buat NFA untuk bahasa: “string biner yang mengandung substring 01”.
Referensi
- Rachmatika, Rinna, S.Kom., M.Kom. Modul Teori Bahasa dan Automata. Universitas Pamulang.