Which of the following CFG(s) is/are in Chomsky Normal form (All capital…

Chomsky Normal Form (CNF) rules: every production must be either of the form A → BC (two variables) or A → a (single terminal).

• Grammar with productions S → ABC | AB; A → a; B → b; C → d: Not in CNF because S → ABC has three variables on the right-hand side, while CNF allows only two variables on the right-hand side.

• Grammar with productions X → RT | TR; T → t; R → XT | r: This is in CNF because each production is either two variables on the right-hand side (X → RT, X → TR, R → XT) or a single terminal (T → t, R → r).

• Grammar with productions P → qP | sQ; Q → r | s: Not in CNF because P → qP has a terminal followed by a variable on the right-hand side. CNF does not permit mixing terminals and variables in one production.

• Grammar with productions M → MN | MP; N → nm | n; P → p: Not in CNF because N → nm has two terminals on the right-hand side. CNF allows only a single terminal on the right-hand side, not two terminals together.

Conclusion: Only the grammar with productions X → RT | TR; T → t; R → XT | r satisfies the CNF restrictions.