Question

Convert the following Context-Free Grammar (CFG) into an equivalent CFG in Chomsky Normal Form.

a→bab∣aba∣b
b→00

A) S→XY∣X
X→ab
Y→b

B) S→AB∣BC
A→ab
B→ba
C→b

C) S→AB∣AC∣D
A→ab
B→ba
C→b
D→00

D) S→AB∣AC
A→ab
B→ba
C→b

Answer 1

Option C is the correct alternative when converting the given CFG into Chomsky Normal Form, as it includes the necessary production rules and adheres to the CNF rule structure.

Step-by-step explanation:

The question asks to convert a given Context-Free Grammar (CFG) into an equivalent CFG in Chomsky Normal Form (CNF). Chomsky Normal Form is a way of writing grammars where every production rule is of the form A → BC or A → a, where A, B, and C are non-terminal symbols, and a is a terminal symbol. Option C is the correct alternative when converting the given CFG into Chomsky Normal Form, as it includes the necessary production rules and adheres to the CNF rule structure.

Additionally, B and C cannot be the start symbol. Since the production rule a → bab | aba | b has the rule a → b, only Option C has an equivalent rule D → 00, making it the right answer after adding a rule for a which is A → ab. Option C then correctly produces the original rules with non-terminal symbols only on the right side in sets of two or a single terminal symbol.