1.1k views
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.1k views
0
ANS----49
+1
yes 49.

Simply $(n+1)a,s\times (n+1)b,s+1$ i.e. 49.
0
how you are getting this formula? please explain
0
It is kind of bruite force.

Try for minimum state Dfa in set of all strings of a's and b's with exactly 2 a's and 3 b's =13

Try for minimum state Dfa in set of all strings of a's and b's with exactly 3 a's and 4 b's=21

Like this you can formulate.
0

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.

by Veteran (57.3k points)
edited by
0
You have missed some transitions, but , even though its right .
+1
Oh sorry all other goes to trap, i forgot in excitement :D
0
why this cannot be 5*7=35 states
+1
very well explained brooo