The correctness of a statement related to the Pumping Lemma and regular language

Question

I was studying Automata theory and came across the Pumping Lemma, which I understand as:

Let $\mathcal{A}=\langle\Sigma, Q, q_0, F, \delta\rangle$ be an NFA. Suppose $x \in L(\mathcal{A})$ s.t. $|x| \geq |Q|$, Then x can be partitioned into $u, v, w, |v| \geq 1$, s.t. $x=uvw$ and for every $i \geq 0$, $uv^iw \in L(\mathcal{A})$

It got me to think whether the following statement is correct:

Let $L$ be a language. If for every word $x \in L$, there is $u, v, w$, s.t. $uvw = x$ and for every $i \geq 0$, $uv^iw \in L$, then $L$ is regular

My idea is that no matter what $u, v, w$ we choose to partition $x$, we can always construct NFAs that accept $u, v, w$, respectively. And we can also construct an NFA that accepts $v^i$ for $i \geq 0$. So if we take the union of the NFAs, we get $A_x = \bigcup^{}_{uvw\ s.t\ uvw=x}A_{uvw}$, where $A_{uvw}$ is the NFA that accepted the words of form $uv^iw$, for $i \geq 0$, if $uvw = x$. Taking Union of theses NFAs, we get $A_x$, which is the NFA that take care of all possible words generated by $x$. The final NFA is then $A = \bigcup{}_{x \in L} A_x $, so $L$ is regular.

But I am really new to the Automata theory, so I'm not sure if my idea is correct. Any answer is appreciated, thanks in advance.

Answer 1

Your claim is false because if you take $v=1$, the your condition is trivially satisfied. Now, if your question is whether a language satisfying the pumping lemma is necessarily regular, the answer is also negative. I let you verify that the language $$ L = \{(ab)^nc^n \mid n>0\} \cup A^*bbA^* \cup A^*aaA^* $$ is not regular, but satisfies the pumping lemma.

If you want a necessary and sufficient condition, you need a more sophisticated version of the pumping lemma. See for instance [1, 2, 3].

[1] J. Jaffe, A necessary and sufficient pumping lemma for regular languages, Sigact News - SIGACT 10 (1978) 48-49.

[2] A. Ehrenfeucht, R. Parikh, and G. Rozenberg, Pumping lemmas for regular sets, SIAM J. Comput. 10 (1981), 536-541.

[3] S. Varricchio, A pumping condition for regular sets, SIAM J. Comput. 26 (1997) 764-771.

Answer 2

The problem with your condition is that you could have an infinite number of $u$s (and an infinite number of corresponding $w$s). Although you can construct an NFA that will accept each individual $u$, you cannot always construct an NFA that will accept any one of an infinite number of $u$s. If you could, then the union of any infinite set of regular languages would be regular, and hence all languages would be regular !

To fix your condition for regularity, you need have an additional constraint that ensures the number of possible $u$s and $w$s is finite.