Virtual Labs

What is a context-free grammar (CFG)?

a: A grammar where each production rule has a single non-terminal on the left side Explanation

Explanation

b: A grammar that can only generate regular languages Explanation

Explanation

c: A grammar that requires context to generate strings Explanation

Explanation

d: A grammar that can only generate finite languages Explanation

Explanation

What is Chomsky Normal Form (CNF)?

a: A form of grammar where all rules are of the form A → BC or A → a Explanation

Explanation

b: A form of grammar that can only generate regular languages Explanation

Explanation

c: A form of grammar that requires context to generate strings Explanation

Explanation

d: A form of grammar that can only generate finite languages Explanation

Explanation

What is the purpose of the CYK algorithm?

a: To convert a context-free grammar to Chomsky Normal Form Explanation

Explanation

b: To determine if a string can be generated by a context-free grammar Explanation

Explanation

c: To generate all possible strings from a grammar Explanation

Explanation

d: To minimize a context-free grammar Explanation

Explanation

What is the time complexity of the CYK algorithm?

a: O(n²) Explanation

Explanation

b: O(n³|G|) Explanation

Explanation

c: O(2ⁿ) Explanation

Explanation

d: O(n log n) Explanation

Explanation

What is the space complexity of the CYK algorithm?

a: O(n) Explanation

Explanation

b: O(n²|N|) Explanation

Explanation

c: O(n³) Explanation

Explanation

d: O(2ⁿ) Explanation

Explanation

In the CYK algorithm, what does each cell (i,j) in the table represent?

a: The length of the substring starting at position j Explanation

Explanation

b: The set of non-terminals that can generate the substring starting at position j with length i Explanation

Explanation

c: The number of production rules used to generate the substring Explanation

Explanation

d: The position of the first terminal in the substring Explanation

Explanation

How do you determine if a string is accepted by the grammar using the CYK algorithm?

a: Check if the last cell contains any non-terminals Explanation

Explanation

b: Check if the start symbol S is in the cell (n,1) Explanation

Explanation

c: Check if all cells in the first row contain non-terminals Explanation

Explanation

d: Check if the number of cells equals the length of the string Explanation

Explanation

What is the first step in the CYK algorithm?

a: Fill the first row with non-terminals that can generate the corresponding terminals Explanation

Explanation

b: Check if the grammar is in Chomsky Normal Form Explanation

Explanation

c: Convert the grammar to Chomsky Normal Form Explanation

Explanation

d: Initialize all cells with empty sets Explanation

Explanation

When filling a cell (i,j) in the CYK table, what do we need to consider?

a: Only the production rules that start with the current non-terminal Explanation

Explanation

b: All possible ways to split the substring into two parts Explanation

Explanation

c: Only the terminals in the current position Explanation

Explanation

d: The previous cell's contents Explanation

Explanation

CYK Algorithm