0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

Your answer is correct.
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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Rodrigo Dec 12 '15 at 15:32
  • $\begingroup$ 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. $\endgroup$ – Yinon Eliraz Dec 12 '15 at 20:10
  • $\begingroup$ 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? $\endgroup$ – Rodrigo Dec 13 '15 at 12:19
  • $\begingroup$ 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. $\endgroup$ – Yinon Eliraz Dec 14 '15 at 12:58

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.