Chapter 0 Little Quiz

1. Which of the following machines or models can implement all possible steps executable by modern computers?
UNIVAC computer Finite automata Turing machine Context-free grammar

2. Which of the following types of problems can be solved in reasonable time?
Undecidable problem Intractable problem Tractable problem Impossible problem

3. Which of the following fields is not in the scope of the theory of computation?
Automata theory Formal languages Information processing Computational complexity

4. Which of the following developments is irrelevant to advance of the theory of computation?
Stored-program computer Robot Turing machine Grammar

5.Which of the following is not an automata model?
Acceptor Transducer Recorder Generator