The question:
Let it be \(\displaystyle L\) a regular language.
few definitions:
\(\displaystyle p(L)\)-the minimal natural number so that \(\displaystyle L\) fulfill the pumping lemma.
\(\displaystyle n(L)\)- minimal NFA that accepts \(\displaystyle L\).
\(\displaystyle m(L)\)- \(\displaystyle Rank(L)\), the number of equivalence classes in \(\displaystyle L\).
Let it be integer \(\displaystyle k>0\). find an example for a language \(\displaystyle L\) so that: \(\displaystyle p=n=m=k\).
My attempt:
At start, thought of \(\displaystyle L=\{w: |w|\bmod k=0\}, \Sigma=\{ a\}\).
But then I realized that \(\displaystyle p<k\).
And also- for every \(\displaystyle L\) that I choose here, I don't know how exactly to prove that the \(\displaystyle NFA\) which accepts it is minimal. I know how to do this only on \(\displaystyle NFA\)'s with one or two states, but not on \(\displaystyle NFA\)'s with unknown number of states.
How can I solve this?
Let it be \(\displaystyle L\) a regular language.
few definitions:
\(\displaystyle p(L)\)-the minimal natural number so that \(\displaystyle L\) fulfill the pumping lemma.
\(\displaystyle n(L)\)- minimal NFA that accepts \(\displaystyle L\).
\(\displaystyle m(L)\)- \(\displaystyle Rank(L)\), the number of equivalence classes in \(\displaystyle L\).
Let it be integer \(\displaystyle k>0\). find an example for a language \(\displaystyle L\) so that: \(\displaystyle p=n=m=k\).
My attempt:
At start, thought of \(\displaystyle L=\{w: |w|\bmod k=0\}, \Sigma=\{ a\}\).
But then I realized that \(\displaystyle p<k\).
And also- for every \(\displaystyle L\) that I choose here, I don't know how exactly to prove that the \(\displaystyle NFA\) which accepts it is minimal. I know how to do this only on \(\displaystyle NFA\)'s with one or two states, but not on \(\displaystyle NFA\)'s with unknown number of states.
How can I solve this?