Match List I with List II. List I: A. A → aB | a (a ∈ T; A, B ∈ V), B. A → BC | a (a ∈ T; A, B, C ∈ V), C. LL(1) grammar, D. Halting problem. List II: I. Recursive descent parser, II. Turing machine, III. Chomsky Normal Form, IV. Finite automata.

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

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

Show answer & explanation

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

Explanation

A → aB | a is a right-linear (regular) grammar, equivalent to a finite automaton. A → BC | a is Chomsky Normal Form. LL(1) grammars are parsed by (predictive) recursive descent. The halting problem concerns Turing machines.