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
Answer
Answer: b [Reason:] Bounded information refers to one whose output is limited and it cannot be said what were the recorded outputs previously until memorized.
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
Answer
Answer: b [Reason:] A language for which there is no existence of a deterministic finite automata is always Non Regular and methods like Pumping Lemma can be used to prove the same.
3. A DFA cannot be represented in the following format
a) Transition graph
b) Transition Table
c) C code
d) None of the mentioned
Answer
Answer: d [Reason:] A DFA can be represented in the following formats: Transition Graph, Transition Table, Transition tree/forest/Any programming Language.
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
Answer
Answer: a [Reason:] Strings such as {1101,101,10101} are being accepted while {1001,11001} are not. Thus, this conclusion leads to option a.
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
Answer
Answer: c [Reason:] Two states are said to be equivalent if and only if they have same number of states as well as transitions.
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
Answer
Answer: c [Reason:] The figure represents the initial as well as the final state with an iteration of x.
7. Which of the following will not be accepted by the following DFA?
a) ababaabaa
b) abbbaa
c) abbbaabb
d) abbaabbaa
Answer
Answer: a [Reason:] All the Strings are getting accepted except ‘ababaabaa’ as it is directed to dumping state. Dumping state also refers to the reject state of the automata.
8. Which of the following will the given DFA won’t accept?
a) ε
b) 11010
c) 10001010
d) String of letter count 11
Answer
Answer: a [Reason:] As the initial state is not made an acceptance state, thus ε will not be accepted by the given DFA. For the automata to accept ε as an entity, one should make the initial state as also the final state.
9. Can a DFA recognize a palindrome number?
a) Yes
b) No
c) Yes, with input alphabet as ∑*
d) Can’t be determined
Answer
Answer: b [Reason:] Language to accept a palindrome number or string will be non-regular and thus, its DFA cannot be obtained. Though, PDA is possible.
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
Answer
Answer: d [Reason:] Proper and sequential combination of events leads the machines to work in hand which includes The elevator, Combinational Locks, Traffic Lights, vending machine, etc. Other applications of Finite machine state system are Communication Protocol Design, Artificial Intelligence Research, A Turnstile, etc.
Set 2
1. If the number of steps required to solve a problem is O(nk), then the problem is said to be solved in:
a) non-polynomial time
b) polynomial time
c) infinite time
d) none of the mentioned
Answer
Answer: b [Reason:] Most of the operations like addition, subtraction, etc as well as computing functions including powers, square roots and logarithms can be performed in polynomial time. In the given question, n is the complexity of the input and k is some non negative integer.
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
Answer
Answer: a [Reason:] The value of such constants can be calculated using algorithms which have time complexity in terms if O(nk) 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
Answer
Answer: d [Reason:] In graph theory, a matching or independent edge set in a graph G is a set of edges without common vertices. Given a graph (V, E), a matching M in G is a set of pairwise non adjacent edges i.e. no two edges share a common vertex.
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
Answer
Answer: d [Reason:] All the decision problems that can be solved using a Deterministic turing machine using polynomial time to compute, all belong to the complexity class P.
5. A generalization of P class can be:
a) PTIME
b) DTIME
c) NP
d) None of the mentioned
Answer
Answer: c [Reason:] P is a specific case of NP class, which is the class of decidable problems decidable by a non deterministic turing machine that runs in polynomial time.
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
Answer
Answer: d [Reason:]
The notion of P-complete decision problems is useful in the analysis of:
a) which problems are tough to parallelize effectively
b) which problems are difficult to solve in limited space
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
Answer
Answer: d [Reason:] A problem X belongs to P complexity class if there exist atleast 1 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. Thus, all the options are correct.
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
Answer
Answer: d [Reason:] Given a context free grammar and a string, can the string be generated by the grammar? Such problems fall in the category of P-complete.
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
Answer
Answer: a [Reason:] If we can parallelize a general simulation of a sequential computer, then we will be able to parallelize any program that runs on that computer. If this problem is in NC, then so every other problem in P.
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
Answer
Answer: c [Reason:] It is the set of all decision problems that have exponential run time i.e. solvable by deterministic turing machine in O(2p(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
Answer
Answer: d [Reason:] A turing machine is abstract or hypothetical machine thought by mathematician Alan Turing in 1936 capable of simulating any algorithm, however complicated it is.
2. A turing machine operates over:
a) finite memory tape
b) infinite memory tape
c) depends on the algorithm
d) none of the mentioned
Answer
Answer: b [Reason:] The turing machine operates on an infinite memory tape divided into cells. The machine positions its head over the cell and reads the symbol.
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
Answer
Answer: d [Reason:] After the read head reads the symbol from the input tape, it performs the following functions:
a) writes a symbol(some model allow symbol erasure/no writing)
b) moves the tape left or right (some models allows no motion)
c) proceeds with subsequent instruction or goes either into accepting halting state or rejecting halting state.
4. ‘a’ in a-machine is :
a) Alan
b) arbitrary
c) automatic
d) None of the mentioned
Answer
Answer: c [Reason:] The turing machine was invented by Alan turing in 1936. He named it as a-machine(automatic machine).
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
Answer
Answer: d [Reason:] Invention of turing machine answered a lot of questions which included problems like decision problem, etc.) . Alan was able to prove the properties of computation using such model.
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
Answer
Answer: a [Reason:] Turing Completeness the ability for a system of instructions to simulate a Turing machine. A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers; nearly all programming languages are Turing complete.
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
Answer
Answer: d [Reason:] We can represent a turing machine, graphically, tabularly and diagramatically.
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
Answer
Answer: d [Reason:] A n abstract machine also known as abstract computer, is a theoretical model of computer or hardware system in automata theory. Abstraction in computing process usually assumes a discrete time paradigm.
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
Answer
Answer: d [Reason:] A thought experiment considers some hypothesis, theory or principle for the purpose of thinking through its consequences.
10. State true or false:
Statement: RAM model allows random access to indexed memory locations.
a) true
b) false
Answer
Answer: a [Reason:] In computer science, Random access machine is an abstract machine in the general class of register machines. Random access machine should not be confused with Random access memory.
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
Answer
Answer: d [Reason:] The class of languages known as the regular language has atleast four different descriptions: i) DFA ii) NFA iii) e-NFA iv) Regular Expressions
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
Answer
Answer: b [Reason:] We use the powerful technique called Pumping Lemma, for showing certain languages not to be regular. We use Ardens theorem to find out a regular expression out of a finite automaton.
3. Which of the following language regular?
a) {aibi|i>=0}
b) {aibi|0<i<5}
c) {aibi|i>=1}
d) None of the mentioned
Answer
Answer: b [Reason:] Here, i has limits i.e. the language is finite, contains few elements and can be graphed using a deterministic finite automata. Thus, it is regular. Others can be proved non regular using Pumping lemma.
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
Answer
Answer: d [Reason:] All of the given languages are regular and finite and thus, can be represented using respective deterministic finite automata. We can also use mealy or moore machine to represent remainders for option c.
5. If L is DFA-regular, L’ is
a) Non regular
b) DFA-regular
c) Non-finite
d) None of the mentioned
Answer
Answer: b [Reason:] This is a simple example of a closure property: a property saying that the set of DFA-regular languages is closed under certain operations.
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
Answer
Answer: b [Reason:] Let L be a regular language. If ~L has k equivalent classes, then any DFA that recognizes L must have atleast k states.
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
Answer
Answer: c [Reason:] In automata theory, the Myphill Nerode theorem provides a necessary and sufficient condition for a language to be regular. The Myphill Nerode theorem can be used to show a language L is regular by proving that the number of equivalence classes of RL(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
Answer
Answer: d [Reason:] The myphill nerode theorem can be generalized to trees and an application of tree automata prove an algorithmic meta theorem about graphs.
9. Given languages:
i) {anbn|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
Answer
Answer: d [Reason:] There is no regular expression that can parse HTML documents. Other options are also non-regular as they cannot be drawn into finite automaton.
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
Answer
Answer: d [Reason:] It is the disadvantage or lack of property of a DFA that it cannot remember an arbitrarily such large amount of data which makes it incapable of accepting such languages like palindrome, reversal, etc.
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
Answer
Answer: b [Reason:] 0101 or 1010 the strings with minimum length on {0,1}* which does not belong to the language of the given regular expression.Other strings like 111, 000, 1101, etc are accepted by the language .
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
Answer
Answer: a [Reason:] What we observe from the question is that, it includes e and 11 and any number of 1’s then. Therefore, its simplifies when we write the same reg. Expression as (11+111)*.
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
Answer
Answer: b [Reason:] It is not required to automate the question if asked theoretically.The number of zeroes fixed is 2. Therefore, we can represent the regular expression as 1*01*01*.
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
Answer
Answer: c [Reason:] According to the given regular expression, e is accepted by its language and it does not end with 00 or 11 or 0 or 1. Thus option a and b are eliminated. Further, the regular expression is valid for the third option.
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
Answer
Answer: b [Reason:] Idempotent Law states that if we take the union of two like expression, we can use a copy of the expression instead i.e. L+L=L. The common arithmetic operators are not idempotent.
6. Which among the following can be an annihilator for multiplication operation?
a) 0
b) 1
c) 100
d) 22/7
Answer
Answer: a [Reason:] An annihilator for an operator is a value such that when the operator is applied to the annihilator and some other value, the result is the annihilator.
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
Answer
Answer: a [Reason:] Lowercase letters near the beginning of an alphabet, a, b and so on are terminal symbols. We shall also assume that digits and other characters such as + or parenthesis are terminals.
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
Answer
Answer: d [Reason:] There are two approaches to infer that certain string are in the language of a certain variable. The most conventional way is to use the rules from body to head, recursive inference. The second approach is expanding the starting variable using one of its productions whose head is tart symbol and derive a string consisting entirely of terminals(head to body or derivations).
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
Answer
Answer: c [Reason:] It completely depends on the person who develops the grammar of any language, how to make use of the tools i.e. leftmost and rightmost derivations.
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
Answer
Answer: a [Reason:] The given form represents leftmost derivations in which at each step we replace the leftmost variable by one of its production bodies.
Total Views: 18
