# Multiple choice question for engineering

## Set 1

1. The language accepted by this DFA is

a) b*ab*ab*ab*

b) (a+b)*

c) b*a(a+b)*

d) b*ab*ab*

### View Answer

2. The minimum state automaton equivalent to the above FSA has the following number of states

a) 1

b) 2

c) 3

d) 4

### View Answer

3. Which one of the following is TRUE?

a) The language L={a^n b^n |n>0 } is regular

b) The language L={a^n |n is prime } is regular

c) The language L={w|w has 3k+1 b’s for some k } is regular

d) None of the mentioned

### View Answer

4.

a) q0, q1,q2

b) q0,q1

c) q0,q1,q2,q3

d) q3

### View Answer

5. Which of the regular expressions given below represent the following DFA?

I) 0*1(1+00*1)*

II) 0*1*1+11*0*1

III) (0+1)*1

a) I and II only

b) I and III only

c) II and III only

d) I II III

### View Answer

(I) and (III) represent DFA.

(II) doesn’t represent the DFA since it accepts strings like 11011, but the regular expression doesn’t accept.

6. Let L1 = {w ∈ {0,1}∗ | w has at least as many occurrences

of (110)’s as (011)’s}.

Let L2 = { ∈ {0,1}∗ | w has at least as many occurrences

of (000)’s as (111)’s}.

Which one of the following is TRUE?

a) L1 is regular but not L2

b) L2 is regular

c) L1 and L2 are regular

d) Neither of them are regular

### View Answer

7. The length of the shortest string NOT in the language (over Σ = {a, b}) of the following regular expression is _____________

a*b*(ba)*a*

a) 2

b) 3

c) 4

d) 5

### View Answer

8. Consider the machine M: The language recognized by M is :

a) {w ∈ {a, b}* / every a in w is followed by ex¬actly two b’s}

b) {w ∈ {a, b}* every a in w is followed by at least two b’}

c) {w ∈ {a, b}* w contains the substring ‘abb’}

d) {w ∈ {a, b}* w does not contain ‘aa’ as a substring}

### View Answer

9. Consider the following deterministic finite state automaton M.

S denotes the set of seven bit in which the 1st ,4th and last bits are 1. The number of strings that are accepted by M is

a) 1

b) 5

c) 7

d) 8

### View Answer

## Set 2

1. S –> aSa| bSb| a| b ;the language generated by the above grammar is the set of

a) All palindromes.

b) All odd length palindromes

c) Strings beginning and ending with the same symbol

d) All even length palindromes

### View Answer

2. Which one of the following languages over the alphabet {0, 1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?

a) strings with the substring 00

b) strings with at most two 0’s

c) strings with at least two 0’s

d) strings beginning and ending with either 0 or 1

### View Answer

3. Which one is a FALSE statement?

a) There exists a unique DFA for every regular language

b) NFA can always are converted to a PDA

c) Complement of CFL is always recursive

d) Every NDFA can be converted to a DFA

### View Answer

4. Match the following

Group 1 Group 2 P. Regular expression 1. Syntax analysis Q. Pushdown automata 2. Code generation R. Dataflow analysis 3. Lexical analysis S. Register allocation 4. Code optimization

a) P-4. Q-1, R-2, S-3

b) P-3, Q-1, R-4, S-2

c) P-3, Q-4, R-1, S-2

d) P-2, Q-1, R-4, S-3

### View Answer

5. Let L = L1 ∩ L2, where L1 and L2 are languages as defined below:

L1 = {ambmcanbn | m, n >= 0 }

L2 = {aibjck | i, j, k >= 0 }

Then L is

a) Not recursive

b) Regular

c) Context free but not regular

d) None of the mentioned

### View Answer

6. Convert the NFA to DFA

a)

b)

c) All of the mentioned

d) None of the mentioned

### View Answer

7. Does epsilon ring any change in the automata

a) Yes

b) No

### View Answer

## Set 3

1. Examine the following DFA: If input is 011100101, which edge is NOT traversed?

a) A B

b) C

c) C D

d) D A

### View Answer

2. If string s is accepted by this DFA, which of these strings cannot be suffix of s?

a) 111001

b) 111111

c) 111000

d) 101010

### View Answer

3. Find the pair of regular expressions that are equivalent

a) (0+1)* and (0*+1*)*

b) (0+1)* and (0+1*)*

c) (0+10)* and (0*+10)*

d) All of the mentioned

### View Answer

4. Which of the following strings is NOT in the Kleene star of the language {011, 10, 110}?

a) 01

b) 10

c) 110

d) 10011101

### View Answer

5. Which grammar is not regular

a) 0^n

b) 0^n 1^n n

c) 0^m 0^n n

d) 0^n 0^n n

### View Answer

6. If is a language, and is a symbol, then, the quotient of and, is the set of strings such that is in: is in. Suppose is regular, which of the following statements is true?

a) L/a is always a regular language

b) L/a is not a regular language

c) Both of the mentioned

d) None of the mentioned

### View Answer

7. Here is a context-free grammar G: S → AB A → 0A1 | 2 B → 1B | 3A which of the following strings are in L (G)?

a) 021300211

b) 022111300211

c) None of the mentioned

d) Both of the mentioned

### View Answer

8. The parse tree below represents a rightmost derivation according to the grammar S → AB, A → aS|a, B → bA. Which of the following are right-sentential forms corresponding to this derivation?

a) aAbAba

b) aababa

c) aABba

d) aSba

### View Answer

9. The grammar G: S → SS | a | b is ambiguous. Check all and only the strings that have exactly two leftmost derivations in G

a) bbb

b) ab

c) All of the mentioned

d) None of the mentioned

### View Answer

10. For the following grammar: S → A | B | 2 A → C0 | D B → C1 | E C → D | E | 3 D → E0 | S E → D1 | S Identify all the unit pairs

a) D,C

b) A,B

c) B,C

d) A,C

### View Answer

## Set 4

1. Which NDFA correctly represents the following RE

a(bab)*∪a(ba)*

a)

b)

c)

d) None of the mentioned

### View Answer

2. Which is the correct NDFA for the following mentioned expression? (ab)*∪(aba)*.

a)

b)

c)

d) None of the mentioned

### View Answer

3. NDFAs where introduced by ____________

a) Michael O Rabin & Dana Scott

b) Dan Brown

c) Sun micro system Labs

d) SAP Labs

### View Answer

4. The regular languages are not closed under

a) Concatenation

b) Union

c) Kleene star

d) Complement

### View Answer

5. The Tuples for NDFA

a) ∑,Q,q0,F,δ

b) Q,q0,F,δ

c) Θ,Q,q0,F,δ

d) F,Q,Δ,q0, δ

### View Answer

6. NFAs are ___ DFAs

a) Larger than

b) More expressive than

c) Less expressive than

d) Equally expressive as

### View Answer

7. An NFA’s transition function returns

a) A Boolean value

b) A state

c) A set of states

d) An edge

### View Answer

## Set 5

1. L1 is accepted by the NFA, obtained by changing the accepting state of M to a non-accepting state and vice versa. Which of the following statements is true?

a) L1 = {0, 1}* – L

b) L1 = {0, 1}* – L

c) L1 ⊆ L

d) L1=L

### View Answer

2. Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least

a) N^{2}

b) 2^{N}

c) 2N

d) N!

### View Answer

3. What can be said about a regular language L over {a} whose minimal finite state automaton has two states?

a) L must be {an| n is odd}

b) L must be {an| n is even}

c) L must be {an| n is even}

d) Either L must be {an | n is odd}, or L must be {an | n is even}

### View Answer

4. How many minimum states are required to find whether a string has odd number of 0’s or not

a) 1

b) 2

c) 3

d) 4

### View Answer

5. The number of states in DFA that accepts the language L(M) ∩ L(N) is _________

a) 0

b) 1

c) 2

d) 3

### View Answer

6. Consider alphabet ∑ = {0, 1}, the null/empty string λ and the sets of strings X0, X1 and X0.How are X1 and X2 are related ?

X0 = 1 X1

X1 = 0 X1 + 1 X2

X2 = 0 X1 + {λ}

Which one of the following represents the strings in X0?

a) 10 (0* + (10)*)1

b) 10 (0* + (10)*)*1

c) 10 (0* + (10)*)*1

d) 10 (0 + 10)*1 + 110 (0 + 10)*1

### View Answer

The string “11” is only possible with option (C).

7. Which of the following languages is/are regular?

L1: {wxwR ⎪ w, x ∈ {a, b}* and ⎪w⎪, ⎪x⎪ >0} wR is the reverse of string w

L2: {anbm ⎪m ≠ n and m, n≥0

L3: {apbqcr ⎪ p, q, r ≥ 0}

a) L1 and L3 only

b) L2

c) L2 and L3 only

d) L3 only

### View Answer

8. The reorganizing capability of NDFA and DFA

a) May be different

b) Must be different

c) Must be same

d) None of the mentioned

### View Answer

9. Which of the following is not regular?

a) String whose length is perfect square and consists of 0s

b) Palindromes consisting of 0’s and 1’s

c) All of the mentioned

d) None of the mentioned

### View Answer

10. Which of the following pairs of regular expression are equivalent?

a) 1(01)* and (10)*1

b) X(xx)* and (xx)*x

c) All of the mentioned

d) None of the mentioned