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?

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

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,

enter image description here

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.