11,801 views
5 votes
5 votes
L=  set of all strings of a's and b's with exactly 5 a's and 7 b's

if DFA M accepts L. The least number of states in M is ------------------

1 Answer

Best answer
9 votes
9 votes

It is a 5 by 7 grid with one trap state. Language is consists of 12 length strings and to get one such string, we can choose any 5 spot for a's and rest 7 spot will be for b's. 

Like the following has exactly 2 a's and 2 b's

As we need ( 3 * 3  + 1 ) = 10 states for 2 a's and 2 b's.

Similarly, For 5 a's and 7 b's, we need ( 6 * 8 + 1) = 49 states. 

This problem resembles to a good combinatorial problem of finding no of paths in such a graph from start node to end node.

edited by

Related questions

2 votes
2 votes
2 answers
2
Utk asked Jan 13, 2016
16,110 views
What is the minimum number of states in the DFA for accepting the strings $(a+b)^{*}a(a+b)(a+b)$I draw the following DFA The minimum number of states is 4. The answer giv...
2 votes
2 votes
1 answer
3
rahul sharma 5 asked Nov 9, 2017
936 views
Minimum number of states in DFA where:, Number of a's and Number of b's are even and epsilon is not accepted.Langugae is defined over {a,b}