Is a^i^2 | i>=1 regular?

Question

Though this expression, is accepted by deterministic finite automation, but if we applying pumping lemma on this expression, pumping lemma fails, also this expression have finite states but does not halt and run on continuously, the edges keep making self loops b/w the states as i tends to become larger and when tends to infinity, it does not supposed to be halt. So, for this expression DFA can be drawn but pumping lemma and TM fails. So, tell is this a regular grammar or not?

Answer 1

Actually a DFA cannot be drawn (at least a correct one that is). You're right that the pumping lemma gives a contradiction, it's easy to pump i up or down to make it non-square. If the pumping lemma shows that a language is not regular, then by definition there is no way to draw a DFA to represent that language.

The set of states is infinite, there must be one state to accept a^1, one for a^2, one for a^3 and so on. Then there's all the states between these accepting ones.. it gets messy pretty quickly. Anyways, if the pumping lemma shows a language is not regular (assuming you're applying it properly), then there is no DFA (or regular expression) to represent the language.