# Multiple choice question for engineering

## Set 1

1. Which of the following not an example Bounded Information?

a) fan switch outputs {on, off}

b) electricity meter reading

c) colour of the traffic light at the moment

d) none of the mentioned

### View Answer

2. A Language for which no DFA exist is a________

a) Regular Language

b) Non-Regular Language

c) May be Regular

d) Cannot be said

### View Answer

3. A DFA cannot be represented in the following format

a) Transition graph

b) Transition Table

c) C code

d) None of the mentioned

### View Answer

4. What the following DFA accepts?

a) x is a string such that it ends with ‘101’

b) x is a string such that it ends with ‘01’

c) x is a string such that it has odd 1’s and even 0’s

d) x is a strings such that it has starting and ending character as 1

### View Answer

5. When are 2 finite states equivalent?

a) Same number of transitions

b) Same number of states

c) Same number of states as well as transitions

d) Both are final states

### View Answer

6. What does the following figure most correctly represents?

a) Final state with loop x

b) Transitional state with loop x

c) Initial state as well as final state with loop x

d) Insufficient Data

### View Answer

7. Which of the following will not be accepted by the following DFA?

a) ababaabaa

b) abbbaa

c) abbbaabb

d) abbaabbaa

### View Answer

8. Which of the following will the given DFA won’t accept?

a) ε

b) 11010

c) 10001010

d) String of letter count 11

### View Answer

9. Can a DFA recognize a palindrome number?

a) Yes

b) No

c) Yes, with input alphabet as ∑*

d) Can’t be determined

### View Answer

10. Which of the following is not an example of finite state machine system?

a) Control Mechanism of an elevator

b) Combinational Locks

c) Traffic Lights

d) Digital Watches

### View Answer

## Set 2

1. If the number of steps required to solve a problem is O(n^{k}), then the problem is said to be solved in:

a) non-polynomial time

b) polynomial time

c) infinite time

d) none of the mentioned

### View Answer

2. The value of constants like p and e can be calculated in:

a) polynomial time

b) non-polynomial time

c) cannot be calculated

d) none of the mentioned

### View Answer

^{k}) i.e polynomial time.

3. Which of the following cannot be solved using polynomial time?

a) Linear Programming

b) Greatest common divisor

c) Maximum matching

d) None of the mentioned

### View Answer

4. The complexity class P consist of all the decision problems that can be solved by ___________using polynomial amount of computation time.

a) Push Down automata

b) DFA

c) NDFA

d) Deterministic Turing machine

### View Answer

5. A generalization of P class can be:

a) PTIME

b) DTIME

c) NP

d) None of the mentioned

### View Answer

6. Which of the following options are correct with reference to P-complete problems?

a) used for the problems which are difficult to solve in limited space

b) every problem in P can be reduced to it using proper reductions

c) complete problem for complexity class P

d) all of the mentioned

### View Answer

7. A problem X belongs to P complexity class if there exist ________ algorithm to solve that problem, such that the number of steps of the algorithms bounded by a polynomial in n, where n is the length of the input.

a) 1

b) 2

c) 3

d) all of the mentioned

### View Answer

8. Which of the following is a P-complete type of problem?

a) Circuit Value problem

b) Linear programming

c) Context free grammar membership

d) All of the mentioned

### View Answer

9. State true or false?

Statement: Given a turing machine, an input for the machine, and a number T(unary), does that machine halt on that input within the first T-steps?

The given problem is P-complete.

a) true

b) false

### View Answer

10. In the above problem, if the input is binary, the class the problem belongs?

a) EXPSPACE

b) DLOGTIME

c) EXPTIME-complete

d) All of the mentioned

### View Answer

^{p(n)}) time, where p(n) is a polynomial function of n.

## Set 3

1. A turing machine is a

a) real machine

b) abstract machine

c) hypothetical machine

d) more than one option is correct

### View Answer

2. A turing machine operates over:

a) finite memory tape

b) infinite memory tape

c) depends on the algorithm

d) none of the mentioned

### View Answer

3. Which of the functions are not performed by the turing machine after reading a symbol?

a) writes the symbol

b) moves the tape one cell left/right

c) proceeds with next instruction or halts

d) none of the mentioned

### View Answer

4. ‘a’ in a-machine is :

a) Alan

b) arbitrary

c) automatic

d) None of the mentioned

### View Answer

5. Which of the problems were not answered when the turing machine was invented?

a) Does a machine exists that can determine whether any arbitrary machine on its tape is circular.

b) Does a machine exists that can determine whether any arbitrary machine on its tape is ever prints a symbol

c) Hilbert Entscheidungs problem

d) None of the mentioned

### View Answer

6. The ability for a system of instructions to simulate a Turing Machine is called _________

a) Turing Completeness

b) Simulation

c) Turing Halting

d) None of the mentioned

### View Answer

7. Turing machine can be represented using the following tools:

a) Transition graph

b) Transition table

c) Queue and Input tape

d) All of the mentioned

### View Answer

8. Which of the following is false for an abstract machine?

a) Turing machine

b) theoretical model of computer

c) assumes a discrete time paradigm

d) all of the mentioned

### View Answer

9. Fill in the blank with the most appropriate option.

Statement: In theory of computation, abstract machines are often used in ___________ regarding computability or to analyze the complexity of an algorithm.

a) thought experiments

b) principle

c) hypothesis

d) all of the mentioned

### View Answer

10. State true or false:

Statement: RAM model allows random access to indexed memory locations.

a) true

b) false

### View Answer

## Set 4

1. All the regular languages can have one or more of the following descriptions:

i) DFA ii) NFA iii) e-NFA iv) Regular Expressions

Which of the following are correct?

a) i, ii, iv

b) i, ii, iii

c) i, iv

d) i, ii, iii, iv

### View Answer

2. Which of the technique can be used to prove that a language is non regular?

a) Ardens theorem

b) Pumping Lemma

c) Ogden’s Lemma

d) None of the mentioned

### View Answer

3. Which of the following language regular?

a) {a^{i}b^{i}|i>=0}

b) {a^{i}b^{i}|0<i<5}

c) {a^{i}b^{i}|i>=1}

d) None of the mentioned

### View Answer

4. Which of the following are non regular?

a) The set of strings in {a,b}* with an even number of b’s

b) The set of strings in {a, b, c}* where there is no c anywhere to the left of a

c) The set of strings in {0, 1}* that encode, in binary, an integer w that is a multiple of 3. Interpret the empty strings e as the number 0.

d) None of the mentioned

### View Answer

5. If L is DFA-regular, L’ is

a) Non regular

b) DFA-regular

c) Non-finite

d) None of the mentioned

### View Answer

6. Which of the following options is incorrect?

a) A language L is regular if and only if ~L has finite number of equivalent classes.

b) Let L be a regular language. If ~L has k equivalent classes, then any DFA that recognizes L must have atmost k states.

c) A language L is NFA-regular if and only if it is DFA-regular.

d) None of the mentioned

### View Answer

7. Myphill Nerode does the following:

a) Minimization of DFA

b) Tells us exactly when a language is regular

c) Both (a) and (b)

d) None of the mentioned

### View Answer

_{L}(relation) is finite.

8. Which of the following are related to tree automaton?

a) Myphill Nerode Theorem

b) State machine

c) Courcelle’s Theorem

d) All of the mentioned

### View Answer

9. Given languages:

i) {a^{n}b^{n}|n>=0}

ii) <div>^{n}</div>^{n}

iii) {w∈{a,b}∗| #a(w)=#b(w)}, # represents occurrences

Which of the following is/are non regular?

a) i, iii

b) i

c) iii

d) i, ii, iii

### View Answer

10. Finite state machine are not able to recognize Palindromes because:

a) Finite automata cannot deterministically find the midpoint

b) Finite automata cannot remember arbitarily large amount of data

c) Even if the mid point is known, it cannot find whether the second half matches the first

d) All of the mentioned

### View Answer

## Set 5

1. The minimum length of a string {0,1}* not in the language corresponding to the given regular expression:

(0*+1*)(0*+1*)(0*+1*)

a) 3

b) 4

c) 5

d) 6

### View Answer

2. Which of the following regular expression is equivalent to R(1,0)?

R(1,0)={111*}*

a) (11+111)*

b) (111+1111)*

c) (111+11*)*

d) All of the mentioned

### View Answer

3. The minimum number of 1’s to be used in a regular expression of the given language:

R(x): The language of all strings containing exactly 2 zeroes.

a) 2

b) 3

c) 0

d) 1

### View Answer

4. The given regular language corresponds to which of the given regular language

e+1+(1+0)*0+(0+1)*11

a) The language of all strings that end with 11 or 00

b) The language of all strings that end with 0 or 1

c) The language of all strings which does not end with 01

d) None of the mentioned

### View Answer

5. Statement: If we take the union of two identical expression, we can replace them by one copy of the expression.

Which of the following is a correct option for the given statement?

a) Absorption Law

b) Idempotent Law

c) Closure Law

d) Commutative Law

### View Answer

6. Which among the following can be an annihilator for multiplication operation?

a) 0

b) 1

c) 100

d) 22/7

### View Answer

7. Statement: A digit, when used in the CFG notation, will always be used as a terminal.

State true or false?

a) True

b) False

### View Answer

8. Choose the incorrect process to check whether the string belongs to the language of certain variable or not?

a) recursive inference

b) derivations

c) head to body method

d) All of the mentioned

### View Answer

9. Statement: Left most derivations are lengthy as compared to Right most derivations.

Choose the correct option:

a) correct statement

b) incorrect statement

c) may or may not be correct

d) depends on the language of the grammar

### View Answer

10. A->aAa|bAb|a|b|e

Which among the following is the correct option for the given production?

a) Left most derivation

b) Right most derivation

c) Recursive Inference

d) None of the mentioned