enter image description hereI have made two DFA’s for $ L= \{a^n b^n a | n\ge0\}$.

First one has several states. The second one is accepting an empty string also.

Somebody please guide me the correct one.



Since FSM's can't count identical sequences, I don't think both of your answers would be correct. You can take a look here, (pumping lemma) to prove why $L= \{a^nb^n | n \ge 0 \}$ is not regular, thus you can't write a FSM for it. Also a good example here shows the proof. On the other hand it would be different if you are meaning $a^*b^*a$ which can be written as a FSM.

  • $\begingroup$ My question is : a^n b^n a, if we can draw a NFA i.e. also fine. $\endgroup$ Nov 30 '19 at 16:38
  • $\begingroup$ A NFA is also a FSM, so you I'm pretty sure you can't draw one $\endgroup$ Nov 30 '19 at 17:43
  • $\begingroup$ But you said that "On the other hand it would be different if you are meaning a∗b∗a which can be written as a FSM." $\endgroup$ Nov 30 '19 at 19:32
  • $\begingroup$ Yeah but $a^*b^*a$ is different than $a^nb^na$. If you want the first one it's easy we can write it. $\endgroup$ Dec 1 '19 at 1:41
  • $\begingroup$ Yes its a^*b^*a. I think we don't have a counting problem in this case because number of a's and b's are not equal. $\endgroup$ Dec 1 '19 at 3:05

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.