Match the language class to its recognising machine

Exercise and reference answers

Matching pairs

1. Left

   Regular

   Right

   Finite Automaton (DFA/NFA)

2. Left

   Context-Free

   Right

   Pushdown Automaton

3. Left

   Context-Sensitive

   Right

   Linear Bounded Automaton

4. Left

   Recursive

   Right

   Turing Machine (halts)

5. Left

   Recursively Enumerable

   Right

   Turing Machine (may not halt)