When using the pumping lemma for CFL, we need to choose a string W that is long enough. However, how long is "long enough"?

Question

Answer

W needs to have at least K symbols, where K is the number of non-terminals in the CFG in CNF form.

Answer

W needs to have at least K-1 symbols, where K is the number of non-terminals in the CFG in any form.

Answer

W needs to have at least 2^K symbols, where K is the number of non-terminals in the CFG in any form.

Answer

W needs to have at least 2^(K-1) symbols, where K is the number of non-terminals in the CFG in CNF.

Crowdly