Prove that relates to pumping lemma that I am not sure about

196 Views Asked by At

So,

I will define like in my last post (for a regular language $L$):

We will define $p(L)$ to be the minimal natural number so that a language $L$ fulfill the pumping lemma.
We will also define $n(L)$ to be the minimal NFA (NFA with a minimal number of states) that accepts $L$.

Prove that $p≤n$.

This is my solution, please tell me if I am wrong somewhere:
We can see first that $p$ is the length of the longest string $w$ in $L$, so that the automata won't go into a loop when reading w. I will prove that by contradiction: if exists a longer string $w$ so that the automata won't get into a loop, then $|w|>p$, and $w$ fulfills the pumping lemma.
So exists a break down $xyz$ of $w$ so that $xy^iz∈L$ for all $i$.
But now we will get that $|n|→∞$:
Let it be N a natural number. we will take $i=N+1$ and we know that $xy^{N+1}z∈L$ and also that $xy^{N+1}z$ has no loop for it at the automata, because there is no loop for $xyz$ at the automata. so we get that the automata has at least $N+1$ states, and N was general, so we see that $|n|→∞$, and that is a contradiction because the number of states of a NFA must be finite.

So now that we proved that, let it be $w∈L$ so that $w$ is the longest word that we won't get a loop at the automata that reading it.
So we know that the length of $w$ is at most $p$, and and since we didn't get a loop at the automata for it- we didn't visit any state of it twice.
So we visited at most at all the states of the automata, and that's why $p≤n$.

1

There are 1 best solutions below

2
On BEST ANSWER

I do not see how you can derive that there is no loop recognizing $xy^iz$ for the fact that there is no loop recognizing $xyz$. This being false your proof is not correct.

To prove your statement I think the good way to go is:

  • take the minimal NFA recognizing $L$.
  • take any word $w$ such that $|w|>n$
  • prove that $w$ satisfy the pumping lemma
  • deduce that $n\geq p$