# Multiple choice question for engineering

## Set 1

1. A turing machine with several tapes in known as:

a) Multi-tape turing machine

b) Poly-tape turing maching

c) Universal turing machine

d) All of the mentioned

### View Answer

2. A multitape turing machine is ________ powerful than a single tape turing machine.

a) more

b) less

c) equal

d) none of the mentioned

### View Answer

3. In what ratio, more computation time is needed to simulate multitape turing machines using single tape turing machines?

a) doubly

b) triple

c) quadratically

d) none of the mentioned

### View Answer

4. Which of the following is true for two stack turing machines?

a) one read only input

b) two storage tapes

c) Both (a) and (b)

d) None of the mentioned

### View Answer

5. Which of the following is not a Non deterministic turing machine?

a) Alternating Turing machine

b) Probabalistic Turing machine

c) Read-only turing machine

d) None of the mentioned

### View Answer

6. Which of the turing machines have existential and universal states?

a) Alternating Turing machine

b) Probalistic Turing machine

c) Read-only turing machine

d) None of the mentioned

### View Answer

7. Which of the following is false for Quantum Turing machine?

a) Abstract machine

b) Any quantum algorithm can be expressed formally as a particular quantum turing machine

c) Gives a solution to ‘Is a universal quantum computer sufficient’

d) None of the mentioned

### View Answer

8. A deterministic turing machine is:

a) ambiguous turing machine

b) unambiguous turing machine

c) non-deterministic

d) none of the mentioned

### View Answer

9. Which of the following is true about Turing’s a-machine?

a) a stands for automatic

b) left ended, right end-infinite

c) finite number of tape symbols were allowed

d) all of the mentioned

### View Answer

10. Which of the following is a multi tape turing machine?

a) Post turing Machine

b) Wang-B Machine

c) Oblivious turing Machine

d) All of the mentioned

### View Answer

## Set 2

1. Which of the following options is correct?

Statement 1: Initial State of NFA is Initial State of DFA.

Statement 2: The final state of DFA will be every combination of final state of NFA.

a) Statement 1 is true and Statement 2 is true

b) Statement 1 is true and Statement 2 is false

c) Statement 1 can be true and Statement 2 is true

d) Statement 1 is false and Statement 2 is also false

### View Answer

2. Given Language: L= {ab U aba}*

If X is the minimum number of states for a DFA and Y is the number of states to construct the NFA,

|X-Y|=?

a) 2

b) 3

c) 4

d) 1

### View Answer

3. An automaton that presents output based on previous state or current input:

a) Acceptor

b) Classifier

c) Transducer

d) None of the mentioned.

### View Answer

4. If NFA of 6 states excluding the initial state is converted into DFA, maximum possible number of states for the DFA is ?

a) 64

b) 32

c) 128

d) 127

### View Answer

5. NFA, in its name has ’non-deterministic’ because of :

a) The result is undetermined

b) The choice of path is non-deterministic

c) The state to be transited next is non-deterministic

d) All of the mentioned

### View Answer

6. Which of the following is correct proposition?

Statement 1: Non determinism is a generalization of Determinism.

Statement 2: Every DFA is automatically an NFA

a) Statement 1 is correct because Statement 2 is correct

b) Statement 2 is correct because Statement 2 is correct

c) Statement 2 is false and Statement 1 is false

d) Statement 1 is false because Statement 2 is false

### View Answer

7. Given Language L= {xϵ {a, b}*|x contains aba as its substring}

Find the difference of transitions made in constructing a DFA and an equivalent NFA?

a) 2

b) 3

c) 4

d) Cannot be determined.

### View Answer

8. The construction time for DFA from an equivalent NFA (m number of node)is:

a) O(m^{2})

b) O(2^{m})

c) O(m)

d) O(log m)

### View Answer

9. If n is the length of Input string and m is the number of nodes, the running time of DFA is x that of NFA.Find x?

a) 1/m^{2}

b) 2^{m}

c) 1/m

d) log m

### View Answer

^{2}n).

10. Which of the following option is correct?

a) NFA is slower to process and its representation uses more memory than DFA

b) DFA is faster to process and its representation uses less memory than NFA

c) NFA is slower to process and its representation uses less memory than DFA

d) DFA is slower to process and its representation uses less memory than NFA

### View Answer

## Set 3

1. What does NP stands for in complexity classes theory?

a) Non polynomial

b) Non-deterministic polynomial

c) Both (a) and (b)

d) None of the mentioned

### View Answer

2. The hardest of NP problems can be:

a) NP-complete

b) NP-hard

c) P

d) None of the mentioned

### View Answer

3. Which of the following contains NP?

a) PSPACE

b) EXPSPACE

c) Both (a) and (b)

d) None of the mentioned

### View Answer

4. Travelling sales man problem belongs to which of the class?

a) P

b) NP

c) Linear

d) None of the mentioned

### View Answer

5. State true or false?

Statement: If a problem X is in NP and a polynomial time algorithm for X could also be used to solve problem Y in polynomial time, then Y is also in NP.

a) true

b) false

### View Answer

6. A problem which is both _______ and _________ is said to be NP complete.

a) NP, P

b) NP, NP hard

c) P, P complete

d) None of the mentioned

### View Answer

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

### View Answer

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(n^{1/2})

c) O(n^{k}), k∈N

d) None of the mentioned

### View Answer

^{k}) 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

### View Answer

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

### View Answer

11. Which of the following does not belong to the closure properties of NP class?

a) Union

b) Concatenation

c) Reversal

d) Complement

### View Answer

## Set 4

1. X is a simple mathematical model of a computer. X has unrestricted and unlimited memory. X is a FA with R/W head. X can have an infinite tape divided into cells, each cell holding one symbol.

Name X?

a) Push Down Automata

b) Non deterministic Finite Automata

c) Turing machines

d) None of the mentioned

### View Answer

2. Which of the following is/are not an application of turing machine?

a) Language Recognization

b) Computers of functions on non negative numbers

c) Generating devices

d) None of the mentioned

### View Answer

3. 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

### View Answer

4. Which of the following cannot be a possibility of a TM while it processes an input?

a) Enters accepting state

b) Enters non-accepting state

c) Enters infinite loop and never halts

d) None of the mentioned

### View Answer

5. Pick the odd one out.

a) Subroutines

b) Multiple tracks

c) Shifting over

d) Recursion

### View Answer

6. Which among the following is not true for 2-way infinte TM?

a) tape in both directions

b) Leftmost square not distinguished

c) Any computation that can be performed by 2-way infinite tape can also be performed by standard TM.

d) None of the mentioned

### View Answer

7. Can a turing machine act like a transducer?

a) yes

b) no

### View Answer

8. Which of the following does not exists?

a) Mutitape TM

b) Multihead TM

c) Multidimentional TM

d) None of the mentioned

### View Answer

^{k}directions, for some fixed k and has a finite control, the machine can be called Multidimentional TM.

9. Enumerator is a turing machine with __________

a) an output printer

b) 5 input tapes

c) a stack

d) none of the mentioned

### View Answer

10. For the following language, an enumerator will print:

L={a^{n}b^{n}|n>=0}

a) a^{n}b^{n}

b) {ab, a^{2}b^{2}, a^{3}b^{3}, …}

c) {e, ab, a^{2}b^{2}, a^{3}b^{3}, …}

d) None of the mentioned

### View Answer

11. Complete the following statement:

Statement : A language is turing recognizable if an only if ___________

a) an enumerator enumerates it

b) it is finite

c) both (a) and (b)

d) none of the mentioned

### View Answer

## Set 5

1. Which of the following conversion is not feasible?

a) Regular expression to automaton conversion

b) Automaton to Regular Expression Conversion

c) NFA to DFA

d) None of the mentioned

### View Answer

2. The computation of e-closure of n-states takes ______ time.

a) O(n^{2})

b) O(n^{3})

c) O(2^{n})

d) None of the mentioned

### View Answer

^{2}states.

3. For a _________ state DFA, the time taken for DFA-NFA conversion is O(n).

a) n

b) n^{1/2}

c) n^{2}

d) 2^{n}

### View Answer

4. With reference to Automaton to Regular Expression Conversion, for each of the n rounds, where n is the number of states of DFA, we can _________ the size of the regular expression constructed.

a) double

b) triple

c) quadruple

d) none of the mentioned

### View Answer

^{3}expressions can take time O(n

^{3}4

^{n}), where n =number of states of the DFA.

5. Conversion of regular expression to e-NFA takes ___________ time.

a) linear

b) exponential

c) logarithmic

d) none of the mentioned

### View Answer

^{3}.

6. The conversion of NFA to DFA can be done in:

a) exponential time

b) linear time

c) logarithmic time

d) all of the mentioned

### View Answer

^{3}) time, without changing the number of states.Next, producing to DFA can take exponential time.

7. Which of the following cannot be converted in an ordinary NFA?

a) DFA

b) Regular Expression

c) e-NFA

d) None of the mentioned

### View Answer

8. NFA to DFA conversion is done via

a) Subset Construction method

b) Warshalls Algorithm

c) Ardens theorem

d) None of the mentioned

### View Answer

9. State true or false:

Statement: Regular expression can directly be converted to DFA without intermediate steps.

a) true

b) false

### View Answer

10. Is the following statement correct?

Statement: Thompson construction is used to convert Regular expression to finite automata.

a) Yes

b) No