# Prove about $NFA$ and pumping lemma

The question:
Let it be $L$ a regular language. few definitions:
$p(L)$-the minimum natural number so that $L$ fulfills the pumping lemma.
$n(L)$- minimal NFA that accepts $L$.
$m(L)$- $Rank(L)$, the number of equivalence classes in $L$.

Let it be integer $k>0$. find an example for a language $L$ so that: $p(L)=n(L)=m(L)=k$.

My attempt:
At start, thought of $L=\{w: |w|\bmod k=0\}$, $\Sigma=\{ a\}$.
But then I realized that $p<k$.
And also- for every $L$ that I choose here, I don't know how exactly to prove that the $NFA$ which accepts it is minimal. I know how to do this only on $NFA$'s with one or two states, but not on $NFA$'s with unknown number of states.
How can I solve this?

If $p<k$ then for $w=a..a$ such that $|w|=p<k$, $w\in L$. But as you defined $L$ it is not possible.
In your case $p=k$ because the finite automaton that accepts $L$ has exactly $k$ states. So every word of size $k$ ensures that you pass through at least one state twice. Thus the pumping lemma holds for $p=k$.
Notice that for a word of size $k$ you will pass through $k+1$ states as the start state is "given" for free.
• But if the pumping lemma holds for $k$, then let it be $N=k-1$, and let it be $w∈L$ so that $|w|>=N$. we don't have $w∈L$ so that $w=N=k-1$, and we know that the lemma holds for $|w|>N$. so $k-1$ also fullfils the pumping lemma- contradiction to $p$ definition. Am I wrong here? – Rodrigo Dec 12 '15 at 15:32
• That is not correct. The pumping lemma only works for $w\in L, |w|>=N$ so for $k-1>=|w|$ its not very effective to use the lemma. – Yinon Eliraz Dec 12 '15 at 20:10
• Ok, so I was wrong about the minimal p that fullfil the lemma. But how can you prove that the minimal $NFA$ which accepts it has $k$ states? I can't deduce from what you wrote that it is true. How can you prove that formally? – Rodrigo Dec 13 '15 at 12:19
• Try with a simple example of mod 3 or 4. Then try to understand how does it apply to all $k$. You can prove by induction. – Yinon Eliraz Dec 14 '15 at 12:58