2
$\begingroup$

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.enter image description here

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – dkaeae Mar 7 at 8:25
  • $\begingroup$ Do you mean to say that I should first construct a NFA for the whole problem and then convert it to a DFA? $\endgroup$ – Infinity Mar 7 at 8:44
  • $\begingroup$ 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. $\endgroup$ – dkaeae Mar 7 at 8:46
  • $\begingroup$ I'll try that. But to be honest, I am often confused while constructing a NFA (this might sound weird). $\endgroup$ – Infinity Mar 7 at 8:49
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I am sorry, but I am unable to visualise this $\endgroup$ – Infinity Mar 7 at 6:54
  • $\begingroup$ @infinity I have edited the reply. Hope it's clearer now. $\endgroup$ – olinarr Mar 7 at 7:09
  • 1
    $\begingroup$ Thank you so much :) $\endgroup$ – Infinity Mar 7 at 7:27
  • $\begingroup$ 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? $\endgroup$ – Infinity Mar 7 at 7:28
  • 1
    $\begingroup$ Yeah, I just thought the same, there are certain minimisation algorithms. Thanks for help $\endgroup$ – Infinity Mar 7 at 8:32
1
$\begingroup$

It will accept all string starting and ending with aa including aa and aaa. enter image description here 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.

$\endgroup$

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.