# NFA/DFA for $L= \{a^n b^n a | n\ge0\}$

I 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.

Zulfi.

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.

• My question is : a^n b^n a, if we can draw a NFA i.e. also fine. Nov 30 '19 at 16:38
• A NFA is also a FSM, so you I'm pretty sure you can't draw one Nov 30 '19 at 17:43
• 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." Nov 30 '19 at 19:32
• Yeah but $a^*b^*a$ is different than $a^nb^na$. If you want the first one it's easy we can write it. Dec 1 '19 at 1:41
• 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. Dec 1 '19 at 3:05