Compilers Questions and Answers – Minimization of DFA – 1

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

Answer: a
Explanation: L1* = * which is { }.

2. Choose the correct statement for the following daigram.
Find the final state from the given diagram
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

Answer: c
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 
advertisement
advertisement

a) 1, 2, 3
b) 2, 3, 4
c) 1, 2, 4
d) 1, 3, 4
View Answer

Answer: c
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?
Find the number of occurrences of ‘a’ from the given diagram
a) A,B
b) B
c) C
d) D,C
View Answer

Answer: b
Explanation: The given alphabet contains only one symbol {a} and the given NFA accepts all strings with any number of occurrences of ‘a’.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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?
Find the deterministic finite automation from the given diagram
a) Find the finite state machines from the given diagram
b) Find the valid minimal DFA from the given diagram
c) Find the bb+a from the given diagram
d) Find the accept ‘b’ of string from the given diagram
View Answer

Answer: a
Explanation: Some 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?
Find the string of length n from the given diagram
a) n – 1
b) n
c) n + 1
d) 2n – 1
View Answer

Answer: c
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.

advertisement

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

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

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

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

9. Match the following NFAs with the regular expressions.

 1. ϵ + 0(01*1 + 00) * 01*
 2. ϵ + 0(10 *1 + 00) * 0
 3. ϵ + 0(10 *1 + 10) *1
 4. ϵ + 0(10 *1 + 10) *10 *

Find the regular expressions from the given diagram
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

Answer: c
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. { an b2m | n>=0, m>=0}
II. {an bm |n=2m}
III. {an bm | n!= m}
IV {xcy |x,y€{a,b)*}

a) I and IV
b) I and III
c) I and only
d) IV
View Answer

Answer: a
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.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.