Pertemuan 3

Pretest

• Apa tujuan Hierarki Chomsky?
• Regular language dikenali oleh mesin apa?
• Apa perbedaan umum regular vs context-free?

Modul (Ringkasan Materi)

Hierarki Chomsky mengelompokkan grammar/bahasa menjadi 4 tipe berdasarkan bentuk produksi dan “kekuatan” mesin pengenal.

• Tipe 3 (Regular): produksi sederhana (kanan/kiri linear). Dikenali oleh Finite Automata (FA).
• Tipe 2 (Context-Free / CFG): bentuk umum A → γ (A satu non-terminal). Dikenali oleh Pushdown Automata (PDA).
• Tipe 1 (Context-Sensitive): produksi tidak memendekkan string (|α| ≤ |β|). Dikenali oleh Linear Bounded Automata (LBA).
• Tipe 0 (Unrestricted): produksi paling bebas. Dikenali oleh Turing Machine (TM).

Posttest

• Sebutkan 4 tipe Chomsky dan mesin pengenal masing-masing.
• Tipe mana yang paling “kuat” dan mengapa?
• CFG dikenali oleh automata apa?

Tugas

• Buat tabel 4 baris: (Tipe, Nama Bahasa, Ciri Produksi, Mesin Pengenal).

Referensi

• Rachmatika, Rinna, S.Kom., M.Kom. Modul Teori Bahasa dan Automata. Universitas Pamulang.