Multiple choice question for engineering
Set 1
1. Which of the following is correct?
Statement 1: ε represents a single string in the set.
Statement 2: Ф represents the language that consist of no string.
a) Statement 1 and 2 both are correct
b) Statement 1 is false but 2 is correct
c) Statement 1 and 2 both are false
d) There is no difference between both the statements, ε and Ф are different notation for same reason
Answer
Answer: a [Reason:] ε represents a single string in the set namely, the empty string while Statement 2 is also correct.
2. The appropriate precedence order of operations over a Regular Language is
a) Kleene, Union, Concatenate
b) Kleene, Star, Union
c) Kleene, Dot, Union
d) Star, Union, Dot
Answer
Answer: c [Reason:] If a regular language expression is given, the appropriate order of precedence if the parenthesis is ignored is: Star or Kleene, Dot or Concatenation, Union or Plus.
3. Regular Expression R and the language it describes can be represented as:
a) R, R(L)
b) L(R), R(L)
c) R, L(R)
d) All of the mentioned
Answer
Answer: c [Reason:] When we wish to distinguish between a regular expression R and the language it represents; we write L(R) to be the language of R.
4. Let for ∑= {0,1} R= (∑∑∑) *, the language of R would be
a) {w | w is a string of odd length}
b) {w | w is a string of length multiple of 3}
c) {w | w is a string of length 3}
d) All of the mentioned
Answer
Answer: b [Reason:] This regular expression can be used to eliminate the answers and get the result. The length can be even and as well more than 3 when R= (∑∑∑) (∑∑∑) (particular case).
5. If ∑= {0,1}, then Ф* will result to:
a) ε
b) Ф
c) ∑
d) None of the mentioned
Answer
Answer: a [Reason:] The star operation brings together any number of strings from the language to get a string in the result. If the language is empty, the star operation can put together 0 strings, resulting only the empty string.
6. The given NFA represents which of the following NFA
a) (ab U a) *
b) (a*b* U a*)
c) (ab U a*)
d) (ab)* U a*
Answer
Answer: a [Reason:] The Regular expression (ab U a) * is converted to NFA in a sequence of stages as it can be clearly seen in the diagram. This NFA consist of 8 stated while its minimized form only contains 2 states.
7. Which of the following represents a language which has no pair of consecutive 1’s if ∑= {0,1}?
a) (0+10)*(1+ε)
b) (0+10)*(1+ε)*
c) (0+101)*(0+ε)
d) (1+010)*(1+ε)
Answer
Answer: a [Reason:] All the options except ‘a’ accept those strings which comprises minimum one pair of 1’s together.
8. The finite automata accept the following languages:
a) Context Free Languages
b) Context Sensitive Languages
c) Regular Languages
d) All the mentioned
Answer
Answer: c [Reason:] A finite automaton accepts the languages which are regular and for which a DFA can be constructed.
9. (a + b*c) most correctly represents:
a) (a +b) *c
b) (a)+((b)*.c)
c) (a + (b*)).c
d) a+ ((b*).c)
Answer
Answer: d [Reason:] Following the rules of precedence, Kleene or star operation would be done first, then concatenation and finally union or plus operation.
10. Which of the following regular expressions represents the set of strings which do not contain a substring ‘rt’ if ∑= {r, t}
a) (rt)*
b) (tr)*
c) (r*t*)
d) (t*r*)
Answer
Answer: d [Reason:] As Kleene operation is not on the whole of the substring, it will not repeat and maintain the order of t, r.
11. According to the precedence rules, x-y-z is equivalent to which of the following?
a) (x-y)-z
b) x-(y-z)
c) Both (x-y)-z and x-(y-z)
d) None of the mentioned
Answer
Answer: a [Reason:] In arithmetic, we group two of the same operators from the left, hence x-y-z is equivalent to (x-y)-z and not x-(y—z).
12. Dot operator in regular expression resembles which of the following?
a) Expressions are juxtaposed
b) Expressions are multiplied
c) Cross operation
d) None of the mentioned
Answer
Answer: a [Reason:] Dot operation or concatenation operation means that the two expressions are juxtaposed i.e. there are no intervening operators in between. In fact, UNIX regular expressions use the dot for an entirely different purpose: representing any ASCII character.
13. Which among the following is not an associative operation?
a) Union
b) Concatenation
c) Dot
d) None of the mentioned
Answer
Answer: d [Reason:] It does not matter in which order we group the expression with the operators as they are associative. If one gets a chance to group the expression, one should group them from left for convenience. For instance, 012 is grouped as (01)2.
14.Which among the following is equivalent to the given regular expression?
01*+1
a) (01)*+1
b) 0((1)*+1)
c) (0(1)*)+1
d) ((0*1)1*)*
Answer
Answer: c [Reason:] Using the rules of precedence on the give expression, c is the appropriate choice with the order of: Bracket>Kleene>Dot>Union
Set 2
1. A randomized algorithm uses random bits as input inorder to achieve a _____________ good performance over all possible choice of random bits.
a) worst case
b) best case
c) average case
d) none of the mentioned
Answer
Answer: c [Reason:] A randomized algorithm is an algorithm that employs a degree of randomness as a part of its logic using random bits as inputs and in hope of producing average case good performace.
2. Which of the following options match the given statement:
Statement: The algorithms that use the random input to reduce the expected running time or memory usage, but always terminate with a correct result in a bounded amount of time.
a) Las Vegas Algorithm
b) Monte Carlo Algorithm
c) Atlantic City Algorithm
d) None of the mentioned
Answer
Answer: a [Reason:] The other type of algorithms are probabalistic algorithms, which depending upon the random input, have a chance of producing incorrect results or fail to produce a result.
3. Which of the following are probalistic algorithms?
a) Las Vegas Algorithm
b) Monte Carlo Algorithm
c) Atlantic City Algorithm
d) All of the mentioned
Answer
Answer: d [Reason:] Monte Carlo algorithms are very vast, but only probably correct. On thr other side, Las Vegas algorithms are always correct, but probably fast.
4. Which of the following algorithms are probably correct as well as fast?
a) Las Vegas Algorithm
b) Monte Carlo Algorithm
c) Atlantic City Algorithm
d) All of the mentioned
Answer
Answer: c [Reason:] The atlantic city algorithms which are bounded polynomial time algorithms are probably correct and probably fast. It is correct more than 75% of the times.
5. Prisonner’s dilemma can be related to the following:
a) cooperative behaviour
b) graph theory
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: a [Reason:] Prisonner’s dilemma is a standard example of a game analysed in game theory where rational cooperative behaviour is judged on the basis of rewards and punishment.
6. Unix sort command uses _________ as its sorting technique.
a) Quick Sort
b) Bucket Sort
c) Radix Sort
d) Merge Sort
Answer
Answer: a [Reason:] Quicksort is the method of choice in many applications( Unix sort command) with O(nlogn) in worst case.
7. State true or false:
Statement: A turing machine has the capability of using randomly ‘generated’ numbers.
a) true
b) false
Answer
Answer: a [Reason:] Complexity theories models randomized algorithms as probalistic turing machines. A probalistic turing machine is a non deterministic turing machine which randomly chooses between the available transitions at each point according to some probalistic distribution.
8. For the given algorithm, find the probability of finding after k iterations:
find_a(array A, n, k)
begin
i=0
repeat
Randomly select one element out of n elements
i=i+1
until i=k or a is found
end
a) (1/2)k
b) (1-(1/3))k
c) 1-(1/2)k
d) None of the mentioned
Answer
Answer: c [Reason:] The given is known as Monte Carlo Algorithm. If a is fount, the algorithm succeeds, else the algorith fails. The algorithm doesn not guarantee success but the run time is bounded.
9. Which of the following can be solved in computer science?
a) P=BPP problem
b) NP=co-NP problem
c) Do one way problems exist?
d) All of the mentioned
Answer
Answer: d [Reason:] There exists a list of unsolved problems in computational theory which includes many problems including the ones given.
10. Which of the following can be referred to as applications of Randomized algorithm?
a) Quicksort
b) Min Cut
c) Verifying Matrix Multiplication
d) All of the mentioned
Answer
Answer: d [Reason:] Freivalds algorithm is a probabalistic randomized algorithm we use to verify matrix multiplication. On the other hand, Randomness can be useful in quicksort. If the algorithm selects pivot element uniformaly at random, it has a probably high probabilty of finishing the work in O(nlogn) time regardless of the input.
Set 3
1. L is a regular Language if and only If the set of __________ classes of IL is finite.
a) Equivalence
b) Reflexive
c) Myhill
d) Nerode
Answer
Answer: a [Reason:] According to Myhill Nerode theorem, the corollary proves the given statement correct for equivalence classes.
2. A language can be generated from simple primitive language in a simple way if and only if
a) It is recognized by a device of infinite states
b) It takes no auxiliary memory
c) Both are correct
d) Both are wrong
Answer
Answer: b [Reason:] A language is regular if and only if it can be accepted by a finite automaton. Secondly, It supports no concept of auxiliary memory as it loses the data as soon as the device is shut down.
3. Which of the following does not represents the given language?
Language: {0,01}
a) 0+01
b) {0} U {01}
c) {0} U {0}{1}
d) {0} ^ {01}
Answer
Answer: d [Reason:] The given option represents {0, 01} in different forms using set operations and Regular Expressions. The operator like ^, v, etc. are logical operation and they form invalid regular expressions when used.
4. According to the given language, which among the following expressions does it corresponds to?
Language L={xϵ{0,1}|x is of length 4 or less}
a) (0+1+0+1+0+1+0+1)4
b) (0+1)4
c) (01)4
d) (0+1+ε)4
Answer
Answer: d [Reason:] The extended notation would be (0+1)4 but however, we may allow some or all the factors to be ε. Thus ε needs to be included in the given regular expression.
5. Which among the following looks similar to the given expression?
((0+1). (0+1)) *
a) {xϵ {0,1} *|x is all binary number with even length}
b) {xϵ {0,1} |x is all binary number with even length}
c) {xϵ {0,1} *|x is all binary number with odd length}
d) {xϵ {0,1} |x is all binary number with odd length}
Answer
Answer: a [Reason:] The given regular expression corresponds to a language of binary strings which is of even length including a length of 0.
6. If R represents a regular language, which of the following represents the Venn-diagram most correctly?
a) An Irregular Set
b) R*
c) R complement
d) R reverse
Answer
Answer: b [Reason:] The given diagram represents the Kleene operation over the Regular Language R in which the final states become the initial and the initial state becomes final.
7. The given NFA corresponds to which of the following Regular expressions?
a) (0+1) *(00+11) (0+1) *
b) (0+1) *(00+11) *(0+1) *
c) (0+1) *(00+11) (0+1)
d) (0+1) (00+11) (0+1) *
Answer
Answer: a [Reason:] The transition states shown are the result of breaking down the given regular expression in fragments. For dot operation, we change a state, for union (plus) operation, we diverge into two transitions and for Kleene Operation, we apply a loop.
8. Concatenation Operation refers to which of the following set operations:
a) Union
b) Dot
c) Kleene
d) Two of the options are correct
Answer
Answer: b [Reason:] Two operands are said to be performing Concatenation operation AB = A•B = {xy: x ∈ A & y ∈ B}.
9. Concatenation of R with Ф outputs:
a) R
b) Ф
c) R.Ф
d) None of the mentioned
Answer
Answer: b [Reason:] By distributive property (Regular expression identities), we can prove the given identity to be Ф.
10. RR* can be expressed in which of the forms:
a) R+
b) R-
c) R+ U R-
d) R
Answer
Answer: a [Reason:] RR*=R+ as R+ means the occurrence to be at least once.
Set 4
1. Which among the following is not a UNIX command for regular expressions?
a) ed
b) sed
c) vi
d) none of the mentioned
Answer
Answer: d [Reason:] Regular expressions are used by different commands in Unix like ed, sed, grep, awk, vi, etc. Sed stands for stream editor which is exclusively used for executing scripts.
2. What is the significance of $ used in regular expression in UNIX?
a) Matches the beginning of the line
b) Matches the end of lines
c) Matches any single character
d) None of the mentioned
Answer
Answer: b [Reason:] Regular expression provides more flexibility while matching string patterns. Special characters like ^, $, *, . are very useful.
3. Generate the regular expression to match blank lines
a) / */
b) /bl
c) /^?/
d) /^$/
Answer
Answer: d [Reason:] There are few expressions which provide the utility of matching metacharacters including /^$/ for blank lines, / */ for matching one or more spaces, /^.*$/ for matching an entire line whatever it is.
4. For the given syntax of sed, which among the following is not a correct option?
General syntax of sed: /pattern/action
a) / are used as delimiters
b) pattern refers to a regular expression
c) pattern refers to the string to be matched
d) action refers to the command
Answer
Answer: c [Reason:] In the general syntax of sed, pattern is the regular expression and action refers to the command given (p: prints the line, d: deletes the line, etc).
5. What does grep do in UNIX?
a) It is an editor in UNIX
b) It searches for text patterns
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: b [Reason:] The grep is a standard UNIX utility program that searches through a set of files in search of a text pattern,specified through a regular expression.
6. State true or false:
Statement: A regular expression is a sequence of characters that represent a pattern.
a) true
b) false
Answer
Answer: a [Reason:] Such a generated pattern could be a fixed word or describe something like more general.
7. Which of the following options support the given statement?
Statement: A regular expression could be a fixed word or describe something like more general.
a) This flexibility makes Regular expression invaluable.
b) This flexibility makes the Regular expression unvaluable.
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: a [Reason:] Regular expressions are very much invaluable tools; they can be used to find a particular segment of line in a file and instruct to take certain actions.
8. What does the following segment of code does?
grep -i man heroes.txt
a) manually opens a file called heroes.txt
b) manages heroes.txt
c) search for “man” in the file “heroes.txt”
d) none of the mentioned
Answer
Answer: c [Reason:] grep is a command which finds the pattern in a particular text segment.Here, it scans each line in heroes.txt and looks for an m followed by a and then followed by n.
9. What does “X?” do regular expression operator?
a) Matches zero or more capital X’s.
b) Matches no or one occurence of the capital letter X.
c) Matches one or more capital X’s.
d) All of the mentioned
Answer
Answer: b [Reason:] There are many other common regular expression operators like $, ^, etc. Which have their own respective purposes.
10. Which of the following does not support regular expressions?
a) sed
b) awk
c) emacs
d) none of the mentioned
Answer
Answer: d [Reason:] There are many UNIX tools including vi, Emacs, sed, awk and modern programming languages which support regular expressions.
Set 5
1. Which of the following is analogous to the following?
:NFA and NPDA
a) Regular language and Context Free language
b) Regular language and Context Sensitive language
c) Context free language and Context Sensitive language
d) None of the mentioned
Answer
Answer: a [Reason:] All regular languages can be accepted by a non deterministic finite automata and all context free languages can be accepted by a non deterministic push down automata.
2. Let T={p, q, r, s, t}. The number of strings in S* of length 4 such that no symbols can be repeated.
a) 120
b) 625
c) 360
d) 36
Answer
Answer: b [Reason:] Using the permutation rule, we can calculate that there will be total of 625 permutations on 5 elements taking 4 as the length.
3. Which of the following relates to Chomsky hierarchy?
a) Regular<CFL<CSL<Unrestricted
b) CFL<CSL<Unrestricted<Regular
c) CSL<Unrestricted<CF<Regular
d) None of the mentioned
Answer
Answer: a [Reason:] The chomsky hierarchy lays down the following order: Regular<CFL<CSL<Unrestricted
4. A language is accepted by a push down automata if it is:
a) regular
b) context free
c) both (a) and (b)
d) none of the mentioned
Answer
Answer: c [Reason:] All the regular languages are the subset to context free languages and thus can be accepted using push down automata.
5. Which of the following is an incorrect regular expression identity?
a) R+f=R
b) eR=e
c) Rf=f
d) None of the mentioned
Answer
Answer: b [Reason:] e is the identity for concatenation. Thus, eR=R.
6. Which of the following strings do not belong the given regular expression?
(a)*(a+cba)
a) aa
b) aaa
c) acba
d) acbacba
Answer
Answer: d [Reason:] The string acbacba is unacceptable by the regular expression (a)*(a+cba).
7. Which of the following regular expression allows strings on {a,b}* with length n where n is a multiple of 4.
a) (a+b+ab+ba+aa+bb+aba+bab+abab+baba)*
b) (bbbb+aaaa)*
c) ((a+b)(a+b)(a+b)(a+b))*
d) None of the mentioned
Answer
Answer: c [Reason:] Other mentioned options do not many of the combinations while option c seems most reliable.
8. Which of the following strings is not generated by the given grammar:
S->SaSbS|e
a) aabb
b) abab
c) abaabb
d) None of the mentioned
Answer
Answer: d [Reason:] All the given options are generated by the given grammar. Using the methods of left and right derivations, it is simpler to look for string which a grammar can generate.
9. abb*c denotes which of the following?
a) {abnc|n=0}
b) {abnc|n=1}
c) {anbc|n=0}
d) {abcn|n>0}
Answer
Answer: b [Reason:] Here, the first mentioned b is fixed while the other can be zero or can be repeated any number of time.
10. The following denotion belongs to which type of language:
G=(V, T, P, S)
a) Regular grammar
b) Context free grammar
c) Context Sensitive grammar
d) All of the mentioned
Answer
Answer: b [Reason:] Ant formal grammar is represented using a 4-tuple definition where V= finite set of variables, T= set of terminal characters, P=set of productions and S= Starting Variable with certain conditions based on the type of formal grammar.
