Compilers Questions and Answers – Minimization of DFA – 2


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

1. The language accepted by this DFA is?
Find the initially circle s from the given diagram
a) b*ab*ab*ab*
b) (a+b)*
c) b*a(a+b)*
d) b*ab*ab*
View Answer

Answer: c
Explanation: Initially circle s around b so b* then a then followed by (a+b)*.

2. The minimum state automation equivalent to the below FSA has the following number of states?
Find the below FSA from the given diagram
a) 1
b) 2
c) 3
d) 4
View Answer

Answer: b
Explanation: State q0 can be omitted because it takes the same input as state q1 hence by removing q0 nothing changes.
Find the state q0 from the given diagram
Following is equivalent FSA with 2 states.

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

Answer: c
Explanation: Only for this option we can build a FA.

4. Find the same state 0 from the given diagram
a) q0, q1,q2
b) q0,q1
c) q0,q1,q2,q3
d) q3
View Answer

Answer: a
Explanation: From q0 state ->0 then again remain on the same state 0, then to next state 1and to q2 we get 1.

5. Which of the regular expressions given below represent the following DFA?
Find the least two b’ from the given diagram
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
View Answer

Answer: b
Explanation: 0*1(1+00*1)*
II) 0*1*1+11*0*1
III) (0+1)*1

(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

Answer: A
Explanation: L1 is regular let us considering the string 011011011011 . Number of times 011 has occurred is 4 but also its occurrence is 3. Also if the string is ending with 011 we can make a 110 . Now the next string: 110110110110 in this 110 has occurred 4 times and 011 3 times which already satisfy the .

7. The length of the shortest string NOT in the language (over Σ = {a, b}) of the following regular expression is _____________
a) 2
b) 3
c) 4
d) 5
View Answer

Answer: B
Explanation: baa is not regular so 3.

8. Consider the machine M: The language recognized by M is :
Find the regular expressions of DFA from the given diagram
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

Answer: b
Explanation: We can try some sample strings like aba, abbbabbb.

9. Consider the following deterministic finite state automaton M.
Find the finite state automaton from the given diagram
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

Answer: c
Explanation: Language that can be accepted by DFA is 1001001 1001011, 1001101, 1001111, 1101001, 1111001, 1011001.

Sanfoundry Global Education & Learning Series – Compilers.

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

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 & technical discussions at Telegram SanfoundryClasses.