# DFA which accepts all strings starting and ending with 'aa'

I have to construct a DFA which accepts set of all strings over {a,b} which start and end with 'aa'. I have constructed the following DFA, but it does not accept 'aa' and 'aaa'. How can I make it accept all strings in the language.

• You could always build an NFA which accepts the strings which are missing and then use the standard construction to obtain a DFA out of it. Mar 7, 2019 at 8:25
• Do you mean to say that I should first construct a NFA for the whole problem and then convert it to a DFA? Mar 7, 2019 at 8:44
• If you're familiar enough with the construction, it is probably the more straightforward (and less error-prone) way to do it. Esp. since, in this case, it is only a particular set of words that are missing. Mar 7, 2019 at 8:46
• I'll try that. But to be honest, I am often confused while constructing a NFA (this might sound weird). Mar 7, 2019 at 8:49

One solution could be putting the final state right after the first two states. From there, if an $$a$$ is read you stay in the final state, otherwise you move to a state analogous to $$q_2$$; from there, with two $$a$$s you return to the final state and with a $$b$$ you go back to $$q_2$$.

In short, just picture ($$q_1, a$$) going to $$q_4$$ instead of $$q_2$$. The rest should go unchanged.

This way, the automata should accept strings such as 'aa', 'aaa' and so on. And of course if it reads a 'b' it'll need two more 'a's to return to the final state.

• I am sorry, but I am unable to visualise this Mar 7, 2019 at 6:54
• @infinity I have edited the reply. Hope it's clearer now. Mar 7, 2019 at 7:09
• One more thing comes to my mind is that do you think this is the minimal DFA? If not, can you come up with a minimal DFA for this problem? Mar 7, 2019 at 7:28
• @Infinity I don't know, probably it isn't; but there is an algorithm which takes a DFA and returns the minimal equivalent DFA. You can try that way! Google may help with that. Mar 7, 2019 at 8:30
• Yeah, I just thought the same, there are certain minimisation algorithms. Thanks for help Mar 7, 2019 at 8:32

It will accept all string starting and ending with aa including aa and aaa. First , it should start with aa.So,we want the machine to remember 'aa'.Anything other than this should go to trap state (qt). That we have done in first two states. If nothing is there after this,the string is in accepted state.

After two consecutive a, if another a comes ,it should remain in final state and if b comes it should come out of final state(q2-->b=q3).

Now if another b encounters ,it should loop in same state that is not final state(since we need string ending with aa only).

And if 'a' comes ,again we want the machine to remember 'a'(for this we need new state) so that we can check for next alphabet and if another 'a' comes,it should go back to final state and if not go to q3.