Which is equivalent CFG without useless symbols for the given grammar: S → PQ…

2020

Which is equivalent CFG without useless symbols for the given grammar:

S → PQ | p , P → p

  1. A.

    S → PQ

  2. B.

    S → p

  3. C.

    S → P , P → p

  4. D.

    S → P | p , P → p

Attempted by 97 students.

Show answer & explanation

Correct answer: B

A symbol is useful if it is both generating and reachable.

  1. Generating Symbols: S and P derive terminals (S p, P p). Q has no production rule, so it is non-generating.

  2. Elimination: Since Q is useless, the production S PQ is eliminated.

This leaves S p and P p. Now, P cannot be reached from the start symbol S, making P unreachable. Removing P leaves only S p.

Correct Answer: S p (Option B).

Explore the full course: Niacl Ao It Specialist