Pertemuan 12
Aturan Produksi Tata Bahasa Regular & FSA untuk Tata Bahasa Regular
Pretest
- Apa ciri utama tata bahasa regular?
- Apa beda right-linear dan left-linear grammar?
- Bagaimana hubungan regular grammar dengan finite automata?
Modul (Ringkasan Materi)
Regular Grammar (tipe 3 Chomsky) memiliki aturan produksi yang sederhana, umumnya:
Right-linear: A → aB | a | ε
Left-linear: A → Ba | a | ε
- Regular grammar menghasilkan bahasa regular.
- Bahasa regular dapat dikenali oleh DFA/NFA.
- Konversi Grammar → FSA (gagasan umum): non-terminal menjadi state, produksi menjadi transisi.
Contoh (right-linear):
S → aA | b
A → aS | a
Artinya: buat state S dan A, transisi mengikuti simbol terminal.
Posttest
- Sebutkan bentuk umum produksi regular grammar.
- Kenapa regular grammar ekuivalen dengan finite automata?
- Jika ada produksi A → ε, apa dampaknya pada state accepting?
Tugas
- Ambil 1 regular grammar sederhana, lalu buat FSA ekuivalennya (diagram atau tabel transisi).
Referensi
- Rachmatika, Rinna, S.Kom., M.Kom. Modul Teori Bahasa dan Automata. Universitas Pamulang.