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
- A.
S → PQ
- B.
S → p
- C.
S → P , P → p
- 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.
Generating Symbols:
SandPderive terminals (S → p, P → p).Qhas no production rule, so it is non-generating.Elimination: Since
Qis 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).