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. 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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
d) Merge Sort

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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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: 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}