Automata Theory Multiple Choice Quaestion & Answers (MCQs) set-42

1. Which of the given problems are NP-complete?
a) Node cover problems
b) Directed Hamilton Circuit Problem
c) Both (a) and (b)
d) None of the mentioned

Explanation: Vertex cover or Node cover problem, and Hamilton Circuit problem, both are NP complete type of problems.

2. Give a classic example of the concept of turing complete.
a) lambda calculus
b) C++
c) Lisp
d) All of the mentioned

Explanation: Most of the programming languages, conventional or unconventional are turing complete. Functional languages like Lisp and Haskell are also turing complete.

3. Which aong the following are undecidable theories?
a) The first order theory of boolean algebra
b) The first order theory of Euclidean geomentry
c) The first order theory of hyperbolic geometry
d) The first order theory of the natural number with addition, multiplication, and equality

Explanation: Tarski and Mostowski in 1949, established that the first order theory of natural numbers with addition, multiplication, and equality is an undecidable theory. Others mentioned are decidable theories.

4. Fill in the blank with reference to Rice’s theorem.
For any non-trivial property of __________ no general or effective method can decide whether an algorithm computes it with that property.
a) partial functions
b) piecewise functions
c) both (a) and (b)
d) none of the mentioned

Explanation: A property of partial functions is called trivial if it holds for all partial computable functions or for none, and an effective decision method is called general if it decides correctly for every algorithm.

5. A function f is called __________ if there exists a TM T so that for any n and any input string of length n, T halts in exactly f(n) moves.
a) Step function
b) Step counting function
c) Inplace functions
d) None of the mentioned

Explanation: If f is a step counting function, T is a TM halting in f(n) moves where n is the length of input string.

6. Which among the following can be an example of application of finite state machine(FSM)?
c) Stack
d) None of the mentioned

Explanation: Idle is the state when data in form of packets is send and returns if NAK is received else waits for the NAK to be received.

7. Which of the following is incorrect for the given phrase
Phrase :’solvable by non deterministic algorithms in polynomial time’
a) NP Problems
b) During control flow, non deterministic algorithm may have more than one choice
c) If the choices that non deterministic algorithm makes are correct, the amount of time it takes is bounded by polynomial time.
d) None of the mentioned

Explanation: Primality testing is a simple example. To decide whether a number is prime or not, one simply selects non deterministically a number checks whether factors exist for the number or not.

8. In terms of NTIME, NP problems are the set of decision problems which can be solved using a non deterministic machine in _______ time.
a) O(n)
b) O(n1/2)
c) O(nk), k?N
d) None of the mentioned

Explanation: The complexity class NP can be defined in terms of NTIME as:
NP=O(nk) for k ?N.

9. Which of the following can be used to define NP complexity class?
a) Verifier
b) Polynomial time
c) Both (a) and (b)
d) None of the mentioned

Explanation: NP can be defined using deterministic turing machines as verifiers.

10. Which of the following are not in NP?
a) All problems in P
b) Boolean Satisfiability problems
c) Integer factorization problem
d) None of the mentioned

Explanation: This is a list of some problems which are in NP:
a) All problems in P
b) Decision version of Integer factorization method
c) Graph Isomorphism Problem
d) All NP complete problems, etc.

11. Which of the following is true with reference to semi-infinite tape using a two track tape?
a) Can simulate a two way tape
b) Upper track represents the head-right cells
c) Lower track represents the head-left cells
d) All of the mentioned

Explanation: The upper track represents the cells of the original TM that are at the right of the initial head position. The lower track represents the cells to the left of the initial head position, but in reverse order.

12. Can a single tape turing machine be simulated using deterministic 2-stack turing machine?
a) Yes
b) No
c) Cannot be said
d) none of the mentioned

Explanation: The symbols to left of the head of turing macine being simulated can be stored on the stack while the symbols on the right of the head can be placed on another stack. On each stack, symbols closer to the TM’s head are placed closer to the top of the stack than symbols farther from the TM’s head.

13. State true or false:
Statement: Turing Machine can change symbols on its tape, whereas the FA cannot change symbols on tape.
a) true
b) false

Explanation: The following mentioned is the difference between 2-way FA and TM. Another instance is that TM has a read/write tape head while FA doesn’t.

14. A deterministic turing machine is:
a) ambiguous turing machine
b) unambiguous turing machine
c) non-deterministic
d) none of the mentioned

Explanation: A deterministic turing machine is unambiguous and for every input, there is exactly one operation possible. It is a subset of non-deterministic Turing machines.

15. In what ratio, more computation time is needed to simulate multitape turing machines using single tape turing machines?
a) doubly
b) triple
d) none of the mentioned