Chapter 0 Little Quiz

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

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

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

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

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