A CFG(Context Free Grammar) is said to be in Chomsky Normal Form (CNF), if all…

2018

A CFG(Context Free Grammar) is said to be in Chomsky Normal Form (CNF), if all the productions are of the form A -> BC or A -> a. Let G be a CFG in CNF. To derive a string of terminals of length x, the number of products to be used is , ISRO 2018

  1. A.

    2x - 1

  2. B.

    2x

  3. C.

    2x + 1

  4. D.

    2x

Attempted by 23 students.

Show answer & explanation

Correct answer: A

In Chomsky Normal Form (CNF), every production rule is either A -> BC or A -> a. To derive a string of length x, we need exactly x terminal productions (A -> a). Additionally, to combine these x terminals into a single start symbol using binary rules (A -> BC), we need x - 1 binary productions. Thus, the total number of productions used is x + (x - 1) = 2x - 1.

Explore the full course: Isro