Select Page
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages
Filter by Categories
nmims post
Objective Type Set
Online MCQ Assignment
Question Solution
Solved Question
Uncategorized

# Multiple choice question for engineering

## Set 1

1. Language classes have the following property:
a) Closure property
b) Decision property
c) Closure & Decision property
d) None of the mentioned

### View Answer

Answer: c [Reason:] A decision property of a language class is an algorithm that takes a formal description of a language(e.g., a DFA) and tells whether or not some property holds.

2. Which of the following are decision properties?
a) Emptiness
b) Infiniteness
c) Membership
d) All of the mentioned

### View Answer

Answer: d [Reason:] Emptiness, Infiniteness and Membership are the decision properties of any language class. Example: Is the language L empty? Or Is w, a string belongs to the regular language L?

3. Pick the odd one out of the given properties of a regular language:
a) Kleene
b) Reversal
c) Homomorphism
d) Membership

### View Answer

Answer: d [Reason:] Membership is a decision property of language class while others mentioned like Kleene, Reversal and Homomorphism are Closure properties of language class.

4. For an automata, which of the following are equivalent variants?
DFA,NFA and NFA with epsilon transitions
a) DFA and NFA
b) NFA and epsilon NFA
c) DFA and epsilon NFA
d) All of the mentioned

### View Answer

Answer: d [Reason:] For a given automata, all the formats of representation be it deterministic finite automata or non deterministic finite automata or non deterministic finite automata with epsilon transitions, all are equivalent variants.

5. Which of the following are not meant to specify a regular language?
a) Regular Expression
b) DFA
c) NDFA and epsilon-NFA
d) All of the mentioned

### View Answer

Answer: d [Reason:] It is possible to convert from one specification to another. We can express a regular language in all the given four variants.

6. Which of the following problems do not belong to decision properties?
a) Given two languages, are there strings that are in both
b) Is the language a subset of another regular language
c) Is the language same as another regular language
d) None of the mentioned

### View Answer

Answer: d [Reason:] To give a solution to the mentioned problems, we require decision properties and for some, we need additional tools like minimized automaton and Pumping lemma.

7. Which of the following is a function of Closure properties?
a) Helps construct representations
b) Helps show informally described languages not to be in class
c) Both (a) and (b)
d) None of the mentioned

### View Answer

Answer: c [Reason:] Using closure properties we can give a=solution to many problems like : Is the regular languages L1 and L2 closed on concatenation operation?, etc.

8. Suppose there is a string w=abbab, and there exists a DFA which accepts w. How many stepts will be required to test its membership?
a) 2
b) 1
c) 4
d) None of the mentioned

### View Answer

Answer: If a string belongs to a language, the number of steps required to test that member ship is equal to the length of string i.e. 5.

9. If a DFA has n states and the language contains any string of length n or more, the language is termed as:
a) Infinite
b) Empty
c) Non regular
d) None of the mentioned

### View Answer

Answer: The language is surely finite if it is limited to string of length n or less. This is because there are atleast n+1 states along the path while traversing w(string).

10. State true or false:
Statement: If an n-state DFA accepts a string w of length n or more, then there must be a state that appears twice on the path labeled w from the start state to the final state.
a) true
b) false

### View Answer

Answer: a [Reason:] This occurs because there are atleast n+1 states along the path while traversing the string w.

## Set 2

1. Which of the following technique is used to find whether a natural language isnt recursive ennumerable?
a) Diagonalization
b) Recursive Induction
c) Both (a) and (b)
d) None of the mentioned

### View Answer

Answer: a [Reason:] To find a non recursively ennumerable language, we use the technique of diagonalization.

2. Diagonalization can be useful in:
a) To find a non recursively ennumerable language
b) To prove undecidablility of haltig problem
c) Both (a) and (b)
d) None of the mentioned

### View Answer

Answer: c [Reason:] Diagonalization is a technique we use for the following operations: a) To find a non recursively ennumerable language. b) To prove undecidablility of halting problem.

3. Which of the following are undecidable problems?
a) Determining whether two grammars generate the same language
b) Determining whether a grammar is ambiguous
c) Both (a) and (b)
d) None of the mentioned

### View Answer

Answer: c [Reason:] In contrast we can put up an algorithm for checking whether two FA’s are equivalent and this program can be implemented as a program.

4. Which of the following are incorrect options?
a) Informally, problem is a yes/no question about an infinite set of possible instances
b) Formally, a problem is a language
c) Both (a) and (b)
d) None of the mentioned

### View Answer

Answer: d [Reason:] Example: Does a graph G has a Hamilton cycle? =>Each undirected graph is an instance of Hamilton cycle problem.

5. If a problem has an algorithm to answer it, we call it _________
a) decidable
b) solved
c) recognizable
d) none of the mentioned

### View Answer

Answer: a [Reason:] An algorithm is a TM that halts on all inputs,accepted or not. Putting other way, decidable problems are recursive languages.

6. Which of the following are decidable problems?
a) Can a particular line of code in a program ever be executed?
b) Do two given CFG’s generate the same language
c) Is a given CFG ambiguous?
d) None of the mentioned

### View Answer

Answer: d [Reason:] All of the mentioned problems are undecidable.

7.Which one of the following is true for the given?
A={(M,w)|M is a turing machine that accepts string w}
a) A concrete undecidable problem
b) A is recognizable but not decidable
c) -A is not recognizable
d) All of the mentioned

### View Answer

Answer: d [Reason:] We can proof A to be undecidable using the contradiction method.

8. Which of the following are correct statements?
a) TMs that always halt are known as Decidable problems
b) TMs that are guaranteed to halt only on acceptance are recursive ennumerable.
c) Both (a) and (b)
d) None of the mentioned

### View Answer

Answer: c [Reason:] There are two types of TMs on the basis of halting: Recursive and Recursively Ennumerable(TM may or may not halt,could loop forever).

9. Statement: If L id R.E., Lc needs to be R.E. Is it correct?
a) Yes
b) No
c) Maybe
d) Cannot predict

### View Answer

Answer: b [Reason:] Any recursive ennumerable language is not closed under complementation.

10. Which of the following is true for The Halting problem?
a) It is recursively ennumerable
b) It is undecidable
c) Both (a) and (b)
d) None of the mentioned

### View Answer

Answer: c [Reason:] Halting problem: Does a given Turing machine M halt on a given input w?

11. With reference to binary strings, state true or false:
Statement: For any turing machine, the input alphabet is restricted to {0,1}.
a) true
b) false

### View Answer

Answer: a [Reason:] When turing machines are coded as Binary strings, we are restricted to take any input alphabet except {0,1}.

12. With reference ti enumeration of binary strings, the conversion of binary strings to integer is possible by treating the resulting string as a base ____ integer.
a) 2
b) 8
c) 16
d) All of the mentioned

### View Answer

Answer: a [Reason:] It makes sense to talk about the i-th binary string” and about “the i-th Turing machine. If i makes no sense as a TM, assume the i-th TM accepts nothing.

## Set 3

1. How many languages are over the alphabet R?
a) countably infinite
b) countably finite
c) uncountable finite
d) uncountable infinite

### View Answer

Answer: d [Reason:] A language over an alphabet R is a set of strings over A which is uncountable and infinite.

2. According to the 5-tuple representation i.e. FA= {Q, ∑, δ, q, F}
Statement 1: q ϵ Q’; Statement 2: FϵQ
a) Statement 1 is true, Statement 2 is false
b) Statement 1 is false, Statement 2 is true
c) Statement 1 is false, Statement 2 may be true
d) Statement 1 may be true, Statement 2 is false

### View Answer

Answer: b [Reason:] Q is the Finite set of states, whose elements i.e. the states constitute the finite automata.

3. δˆ tells us the best:
a) how the DFA S behaves on a word u
b) the state is the dumping state
c) the final state has been reached
d) Kleene operation is performed on the set

### View Answer

Answer: a [Reason:] δ or the Transition function describes the best, how a DFA behaves on a string where to transit next, which direction to take.

4. Which of the following option is correct?
A= {{abc, aaba}. {ε, a, bb}}
a) abcbb ₵ A
b) ε₵A
c) ε may not belong to A
d) abca ₵ A

### View Answer

Answer: b [Reason:] As the question has dot operation, ε will not be a part of the concatenated set. Had it been a union operation, ε would be a part of the operated set.

5. For a DFA accepting binary numbers whose decimal equivalent is divisible by 4, what are all the possible remainders?
a) 0
b) 0,2
c) 0,2,4
d) 0,1,2,3

### View Answer

Answer: d [Reason:] All the decimal numbers on division would lead to only 4 remainders i.e. 0,1,2,3 (Property of Decimal division).

6. Which of the following x is accepted by the given DFA (x is a binary string ∑= {0,1})?

a) divisible by 3
b) divisible by 2
c) divisible by 2 and 3
d) divisible by 3 and 2

### View Answer

Answer: d [Reason:] The given DFA accepts all the binary strings such that they are divisible by 3 and 2.Thus, it can be said that it also accepts all the strings which is divisible by 6.

7. Given:
L1= {xϵ ∑*|x contains even no’s of 0’s}
L2= {xϵ ∑*|x contains odd no’s of 1’s}
No of final states in Language L1 U L2?
a) 1
b) 2
c) 3
d) 4

### View Answer

Answer: c [Reason:]

8. The maximum number of transition which can be performed over a state in a DFA?
∑= {a, b, c}
a) 1
b) 2
c) 3
d) 4

### View Answer

Answer: c [Reason:] The maximum number of transitions which a DFA allows for a language is the number of elements the transitions constitute.

9. The maximum sum of in degree and out degree over a state in a DFA can be determined as:
∑= {a, b, c, d}
a) 4+4
b) 4+16
c) 4+0
d) depends on the Language

### View Answer

Answer: d [Reason:] The out degree for a DFA I fixed while the in degree depends on the number of states in the DFA and that cannot be determined without the dependence over the Language.

10. The sum of minimum and maximum number of final states for a DFA n states is equal to:
a) n+1
b) n
c) n-1
d) n+2

### View Answer

Answer: a [Reason:] The maximum number of final states for a DFA can be total number of states itself and minimum would always be 1, as no DFA exits without a final state. Therefore, the solution is n+1.

## Set 4

1. Subset Construction method refers to:
a) Conversion of NFA to DFA
b) DFA minimization
c) Eliminating Null references
d) ε-NFA to NFA

### View Answer

Answer: a [Reason:] The conversion of a non-deterministic automata into a deterministic one is a process we call subset construction or power set construction.

2. Given Language:
Ln= {xϵ {0,1} * | |x|≥n, nth symbol from the right in x is 1}
How many state are required to execute L3 using NFA?
a) 16
b) 15
c) 8
d) 7

### View Answer

Answer: b [Reason:] The finite automaton for the given language is made and thus, the answer can be obtained.

3. Which of the following does the given NFA represent?

a) {11, 101} * {01}
b) {110, 01} * {11}
c) {11, 110} * {0}
d) {00, 110} * {1}

### View Answer

Answer: c [Reason:] The given diagram can be analysed and thus the option can be seeked.

4. The number of transitions required to convert the following into equivalents DFA:

a) 2
b) 3
c) 1
d) 0

### View Answer

Answer: a [Reason:]

5. If L is a regular language, Lc and Lr both will be:
a) Accepted by NFA
b) Rejected by NFA
c) One of them will be accepted
d) Cannot be said

### View Answer

Answer: a [Reason:] If L is a regular Language, Lc and Lr both are regular even.

6. In NFA, this very state is like dead-end non final state:
a) ACCEPT
b) REJECT
c) DISTINCT
d) START

### View Answer

Answer: b [Reason:] REJECT state will be like a halting state which rejects a particular invalid input.

7. We can represent one language in more one FSMs, true or false?
a) TRUE
b) FALSE
c) May be true
d) Cannot be said

### View Answer

Answer: a [Reason:] We can represent one language in more one FSMs, example for a same language we have a DFA and an equivalent NFA.

8. The production of form non-terminal -> ε is called:
a) Sigma Production
b) Null Production
c) Epsilon Production
d) All of the mentioned

### View Answer

Answer: b [Reason:] The production of form non-terminal ->ε is call null production.

9. Which of the following is a regular language?
a) String whose length is a sequence of prime numbers
b) String with substring wwr in between
c) Palindrome string
d) String with even number of Zero’s

### View Answer

Answer: d [Reason:] DFSM’s for the first three option is not possible; hence they aren’t regular.

10. Which of the following recognizes the same formal language as of DFA and NFA?
a) Power set Construction
b) Subset Construction
c) Robin-Scott Construction
d) All of the mentioned

### View Answer

Answer: d [Reason:] All the three option refers to same technique if distinguishing similar constructions for different type of automata.

## Set 5

1. A turing machine that is able to simulate other turing machines:
a) Nested Turing machines
b) Universal Turing machine
c) Counter machine
d) None of the mentioned

### View Answer

Answer: b [Reason:] A more mathematically oriented definition with the same universal nature was introduced by church and turing together called the Church-Turing thesis(formal theory of computation).

2. Which of the problems are unsolvable?
a) Halting problem
b) Boolean Satisfiability problem
c) Both (a) and (b)
d) None of the mentioned

### View Answer

Answer: c [Reason:] Alan turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.

3. Which of the following a turing machine does not consist of?
a) input tape
b) head
c) state register
d) none of the mentioned

### View Answer

Answer: d [Reason:] A state register is one which stores the state of the turing machine, one of the finitely many. Among these is the special start state with which the state register is initialized.

4. The value of n if turing machine is defined using n-tuples:
a) 6
b) 7
c) 8
d) 5

### View Answer

Answer: b [Reason:] The 7-tuple definition of turing machine: (Q, S, G, d, q0, B, F) where Q= The finite set of states of finite control S= The finite set of input symbols G= The complete set of tape symbols d= The transition function q0= The start state, a member of Q, in which the finite control is found initially. B= The blank symbol F= The set of final or accepting states, a subset of Q.

5. If d is not defined on the current state and the current tape symbol, then the machine ______
a) does not halts
b) halts
c) goes into loop forever
d) none of the mentioned

### View Answer

Answer: b [Reason:] If we reach hA or hR, we say TM halts. Once it has halted, it cannot move further, since d is not defined at any pair (hA,X) or (hR,X) where hA = accept halting state and hR = reject halting state.

6. Statement: Instantaneous descriptions can be designed for a Turing machine.
State true or false:
a) true
b) false

### View Answer

Answer: a [Reason:] Inorder to describe formally what a Turing machine does, we need to develop a notation for configurations or Instantaneous descriptions(ID).

7. Which of the following are the models equivalent to Turing machine?
a) Multi tape turing machine
b) Multi track turing machine
c) Register machine
d) All of the mentioned

### View Answer

Answer: d [Reason:] Many machines that might be thought to have more computational capability than a simple UTM can be shown to have no more power. They might compute faster or use less memory but cannot compute more powerfully i.e. more mathematical questions.

8. Which among the following is incorrect for o-machines?
a) Oracle Turing machines
b) Can be used to study decision problems
c) Visualizes Turing machine with a black box which is able to decide cerain decion problems in one operation
d) None of the mentioned

### View Answer

Answer: d [Reason:] In automata theory, an o- machine or oracle machine is a abstract machine used to study decision problems. The problem the oracle solves can be of any complexity class. Even undecidable problems like halting problems can be used.

9. RASP stands for:
a) Random access storage program
b) Random access stored program
c) Randomly accessed stored program
d) Random access storage programming

### View Answer

Answer: b [Reason:] RASP or Random access stored program is an abstract machine that has instances like modern stored computers.

10. Which of the following is not true about RASP?
a) Binary search can be performed more quickly using RASP than a turing machine
b) Stores its program in memory external to its state machines instructions
c) Has infinite number of distinguishable, unbounded registers
d) Binary search can be performed less quickly using RASP than a turing machine
e) More than two options are incorrect

### View Answer

Answer: d [Reason:] In theoretical computer science, the random access stored program( RASP ) machine model is an abstract machine used for the purpose of algorithm development and algorithm complexity theory.

11. State true or false:
Statement: RASP is to RAM like UTM is to turing machine.
a) true
b) false

### View Answer

Answer: a [Reason:] The Rasp is a random access machine model that, unlike the RAM has its program in its registers together with its input. The registers are unbounded(infinite in capacity); whether the number of registers is finite is model-specific.