This set of Compilers Multiple Choice Questions & Answers (MCQs) focuses on “Minimization of DFA – 1”.

1. Consider the languages L1 = and L2 = {a}. Which one of the following represents L1 L2* U L1*

a) €

b) a*

c) All of the mentioned

d) None of the mentioned

View Answer

Explanation: L1* = * which is { }.

2. Choose the correct statement for the following

a) For the language accepted by A which is also a minimal DFA

b) A accepts all strings over {0,1} of length at least 2

c) All of the mentioned

d) None of the mentioned

View Answer

Explanation: The DFA can be minimized to two states and the second state is final state .We reach second state after a 0.

3. Given the language L = {ab, aa, baa}, which of the following strings are in L*?

1) abaabaaabaa

2) aaaabaaaa

3) baaaaabaaaab

4) baaaaabaa

a) 1, 2, 3

b) 2, 3, 4

c) 1, 2, 4

d) 1, 3, 4

View Answer

Explanation: The given alphabet ∑ contains only one symbol {a} and the given NFA accepts all strings with any number of occurrences of ‘a’.

4. W hat is the complement of the language accepted by the NFA shown below?

a) A,B

b) B

c) C

d) D,C

View Answer

Explanation: The given alphabet contains only one symbol {a} and the given NFA accepts all strings with any number of occurrences of ‘a’.

5. A deterministic finite automation (DFA)D with alphabet {a,b} is given below Which of the following finite state machines is a valid minimal DFA which accepts the same language as D?

a)

b)

c)

d)

View Answer

Explanation: Options (B) and (C) are invalid because they both accept ‘b’ as a string which is not accepted by give DFA. D is invalid because it accepts bb+a which are not accepted by given DFA.

6.Let w be any string of length n is {0,1}*. Let L be the set of all substring of w.

State the minimum number of states in a NDFA that accepts L?

a) n-1

b) n

c) n +1

d) 2n-1

View Answer

Explanation: We need minimum n+ 1 state to build NFA that accepts all substrings of a binary string. Following NFA accepts all strings containing substring of “010″ and it has 4 states.

7. 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) String with substring 00

b) string with at most two 0’s

c) string containg at least two 0’s

d) None of the mentioned

View Answer

Explanation: The regular expression has two 0′s surrounded by (0+1)* which means accepted strings must have at least 2 0′s.

8. Which one of the following is FALSE?

a) Every NFA can be converted to DFA

b) Every subset of a recursively enumerable set is recursive

c) All of the mentioned

d) None of the mentioned

View Answer

Explanation: Every subset of a recursively enumerable set is recursive.

9. Match the following NFAs with the regular expressions they correspond to

1. ϵ + 0(01*1 + 00) * 01*

2. ϵ + 0(10 *1 + 00) * 0

3. ϵ + 0(10 *1 + 10) *1

4. ϵ + 0(10 *1 + 10) *10 *

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

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

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

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

View Answer

Explanation: The above figures correctly represent the figures

Eg: p gives ϵ + 0(01*1 + 00) * 01* and the q gives the expression ϵ + 0(10 *1 + 00) * 0 and so on.

10. Which of the following are regular sets?

I. { a^{n} b^{2}m | n>=0, m>=0}

II. {a^{n} b^{m} |n=2m}

III. {a^{n} b^{m} | n!= m}

IV {xcy |x,y€{a,b)*}

a) I and IV

b) I and III

c) I and only

d) IV

View Answer

Explanation: We can write DFA for both I and IV.

**Sanfoundry Global Education & Learning Series – Compilers.**

To practice all areas of Compilers, __here is complete set of 1000+ Multiple Choice Questions and Answers__.