The question :
Given $G$ a context-free grammar of Chomsky normal form with $k$ symbols. We know that the language $L(G)$ satisfy the pumping lemma for $ p = 2^k + 1$
I have those two questions to proove:
1. Show that for each word $w$ in $L(G)$ such as $|w| \geq p$, a word $w'$ exist in $L(G)$ such as $|w'|\lt|w|$ EDIT THIS ONE IS ANSWERED ( SEE COMMENTS, 2 AND 3 LEFT)
In other words, if a word w exist in the language generated by the grammar that has a superior length than the pumping length then an other word w' exist and has a smaller length than w but is in the language.
2. Show that if $L(G) \neq \emptyset$ then a word x exist where $x$ is in $L(G)$ such as $|x| \leq p$
3. Show that this language is decidable $NV_{GNC}$ = {< G >: where G is a context-free grammar in Chomsky normal form and $L(G) \neq \emptyset $ }
This is my proof for 3 ( feel free to correct me if this doesn't work.)
If we have a grammar in Chomsky normal form, H, then it takes H exactly 2n − 1 steps to generate an input of length n. (Unless n = 0, in which case it requires 1 step.) Thus, if G is in Chomsky-normal form, we can design a turing machine that will generate all derivations in G of length 2|w| − 1. Since there are finitely many rules, this can be done in finite time and space. At that point, we only need to check all of our derivations against w; if any one matches, we accept; if none do, we reject.
Note : to answer 2 you can use 1 and to answer 3 you can use 1,2.
I am really not sure what step i need to do to proove that, if anyone could help it would be appreciated.
HINT for 1: Apply the pumping lemma to $w$ and pump down; i.e., in this version of the pumping lemma let $n=0$.
HINT for 2: If not, let $w$ be a word in $L(G)$ of minimal length, and apply 1 to get a contradiction.