# Design a DFA for the language L = {w | w contain 2 a’s at any position and greater than 3 b’s at any position, w ϵ {a.b}*}/

I do not understand this question,because for saving Number of a's and b's memory is required,which FA does not provide.could anybody please explain this?

• It is not required to know the exact amount of 'a', you only need to know is it 0, 1, 2, or more. – Vladislav Mar 12 '20 at 19:37

## 1 Answer

The claim that a DFA does not have memory is incorrect, a DFA in fact has finite "memory" in the sense that you can design the states to have meanings in terms of some variables. (Eg. being in state 5 means you've seen at least 5 a's, so you in some sense remember that you've seen 5 a's)

Now to address the question,

starting at the state marked S and ending at the accepting state (2,4), we move between states incrementing the first index when we see an 'a' and incrementing the second when we see a 'b'. If we run out of string before reaching 2 a's and 4 b's the string gets rejected, or if we see more than 2 a's we move to the trash state.

The only strings that do get accepted are those with exactly 2 a's and at least 4 b's. The different states that we have completely encapsulate all the necessary "memory" in the sense above.