Quiz pilihan ganda sesi 14

Apa tujuan utama transformasi grammar ke bentuk Chomsky Normal Form (CNF)?

• Mempermudah parsing dan analisis grammar

• Menghilangkan semua produksi ke ε

• Menghapus simbol terminal

• Membuat grammar menjadi tidak ambiguitas

Dalam CNF, setiap produksi grammar hanya memiliki bentuk:

• A → BC atau A → a (di mana A, B, C adalah non-terminal dan a terminal)

• A → aB atau A → a

• A → ε atau A → a

• A → B atau A → C

Grammar yang tidak memiliki produk untuk ε selain dari start symbol dapat dikonversi ke CNF dengan:

• Menghilangkan ε-productions dan mengubah aturan lain sesuai kebutuhan

• Menambahkan lebih banyak ε-productions

• Mengubah semua terminal menjadi non-terminal

• Tidak perlu diubah sama sekali

Apa fungsi dari produksi unit dalam grammar?

• Produk yang menghubungkan satu non-terminal ke non-terminal lain secara langsung

• Produksi yang menghasilkan terminal

• Produk yang tidak pernah dipakai

• Produksi yang menghasilkan ε

Dalam proses konversi ke CNF, produksi unit dihilangkan dengan:

• Mengganti langsung dengan produksi non-terminal tujuan unit production

• Mengganti dengan terminal

• Menghilangkan tanpa pengganti

• Menambahkan ε-productions

Pada sebuah grammar, simbol non-terminal dianggap useless jika:

• Tidak pernah menghasilkan string terminal

• Tidak pernah muncul di produksi

• Hanya menghasilkan ε

• Ada di FOLLOW set

Syarat grammar bebas dari useless symbol adalah:

• Semua non-terminal dapat mencapai terminal pada produknya dan dapat dicapai dari start symbol

• Semua non-terminal menghasilkan ε

• Semua terminal menjadi non-terminal

• Semua produksi berisi ε

Dalam metode CYK (Cocke-Younger-Kasami), input yang digunakan adalah:

• Grammar dalam bentuk CNF dan string input

• Grammar biasa dan string input

• Hanya string input

• Hanya grammar biasa

Pada parsing CYK, tabel parsing diisi dengan cara:

• Mengisi entri dengan non-terminal yang bisa menghasilkan substring input tertentu

• Mengisi dengan terminal secara langsung

• Mengisi dengan produksi unit saja

• Mengisi dengan simbol ε

Apakah parsing CYK merupakan teknik top-down atau bottom-up?

• Bottom-up

• Top-down

• Both

• Tidak keduanya