The least number of states in DFA

Question

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 ------------------

Comments

how you are getting this formula? please explain

---

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.

---

with respect to this sir can you please answer https://gateoverflow.in/70749/number-of-states-in-minimal-finite-automata#a70759

Answer 1

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.

Comments

You have missed some transitions, but , even though its right .

---

Oh sorry all other goes to trap, i forgot in excitement :D

---

why this cannot be 5*7=35 states

---

very well explained brooo