GATE CSE 2006 | Question: 34

Question

Consider the regular language $L=(111+11111)^{*}.$ The minimum number of  states in any DFA accepting this languages is:

• A. $3$
• B. $5$
• C. $8$
• D. $9$

Comments

After reading solution, I was like "F*** Awesome Question".

---

Note: The answer is 9 not because there are 9 states in the DFA. It is 9 because 9 is the the minimum number of states in any DFA accepting the language. That means, you need to show that this DFA is not just any DFA, but the minimum DFA, that is, this DFA cannot be minimized further (There are no unreachable states, and each state is distinguishable from every other state so no two states can be merged together).

Watch this video if you don't know how to minimize a DFA.

Answer 1

We can construct the NFA for the language and then construct equivalent DFA. From that we get 9 states for DFA.

Comments

not accepting 1^12.

Answer 2

Hi, this is how I solved this post. Please tell me where I was wrong?

 

Comments

Nothing wrong with your approach, it’s just automaton you have drawn is NFA, and question asked for a DFA,

Convert this NFA to a minimal DFA, and you’ll get correct result.

Answer 3

L = (111 + 11111)* generates the strings {ϵ, 111, 11111, 111111, 11111111, …….}
i.e. it generates any string which can be obtained by repetition of three and five 1’s (means length 3, 6, 8, 9, 10, 11, …}
The DFA for the L = (111 + 11111)* is given below.

Answer 4

1 state in minimal state DFA if only 1 is given as the lone alphabet in the language .if any other alphabets are also given ,then the minimal DFA would have 2 states,one for accepting any number of 1's and other for rejecting other alphabets.