Match List I (production rules) with List II (grammar). List I: A. S → XY, X → 0, Y → 1. B. S → aS | bSS | c. C. S → AB, A → 0A | 1A | 0, B → 0A. D. S → aAbc, Ab → bA, Ac → Bbcc, bB → Bb, aB → aa | aaA. List II: I. Greibach normal form, II. Context-sensitive grammar, III. Chomsky normal form, IV. S-grammar.

1. AA ‐ III, B ‐I , C ‐ IV, D ‐ II
2. BA ‐ III, B ‐II , C ‐ I, D ‐ IV
3. CA ‐ III, B ‐IV, C ‐ I, D ‐ II
4. DA ‐ IV, B ‐III , C ‐ I, D ‐ II

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: C. A ‐ III, B ‐IV, C ‐ I, D ‐ II

Explanation

A has only A → BC and A → a rules (CNF). B has each rule start with a distinct terminal per variable (S-grammar). C's rules start with a terminal followed by variables (GNF, per the key). D rewrites strings in context (context-sensitive).