# 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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

5. If ∑= {0,1}, then Ф* will result to:

a) ε

b) Ф

c) ∑

d) None of the mentioned

### View Answer

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*

### View Answer

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+ε)

### View Answer

8. The finite automata accept the following languages:

a) Context Free Languages

b) Context Sensitive Languages

c) Regular Languages

d) All the mentioned

### View Answer

9. (a + b*c) most correctly represents:

a) (a +b) *c

b) (a)+((b)*.c)

c) (a + (b*)).c

d) a+ ((b*).c)

### View Answer

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*)

### View Answer

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

### View Answer

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

### View Answer

13. Which among the following is not an associative operation?

a) Union

b) Concatenation

c) Dot

d) None of the mentioned

### View Answer

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*)*

### View Answer

## 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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

6. Unix sort command uses _________ as its sorting technique.

a) Quick Sort

b) Bucket Sort

c) Radix Sort

d) Merge Sort

### View Answer

7. State true or false:

Statement: A turing machine has the capability of using randomly ‘generated’ numbers.

a) true

b) false

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

## 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

### View Answer

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

### View Answer

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}

### View Answer

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}

### View Answer

^{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}

### View Answer

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

### View Answer

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) *

### View Answer

8. Concatenation Operation refers to which of the following set operations:

a) Union

b) Dot

c) Kleene

d) Two of the options are correct

### View Answer

9. Concatenation of R with Ф outputs:

a) R

b) Ф

c) R.Ф

d) None of the mentioned

### View Answer

10. RR* can be expressed in which of the forms:

a) R+

b) R-

c) R+ U R-

d) R

### View Answer

## 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

### View Answer

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

### View Answer

3. Generate the regular expression to match blank lines

a) / */

b) /bl

c) /^?/

d) /^$/

### View Answer

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

### View Answer

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

### View Answer

6. State true or false:

Statement: A regular expression is a sequence of characters that represent a pattern.

a) true

b) false

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

10. Which of the following does not support regular expressions?

a) sed

b) awk

c) emacs

d) none of the mentioned

### View Answer

## 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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

6. Which of the following strings do not belong the given regular expression?

(a)*(a+cba)

a) aa

b) aaa

c) acba

d) acbacba

### View Answer

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

### View Answer

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

### View Answer

9. abb*c denotes which of the following?

a) {abnc|n=0}

b) {abnc|n=1}

c) {anbc|n=0}

d) {abcn|n>0}

### View Answer

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