Return to Answer

After 2 failed attempts, that were disproved by @Hendrik Jan (thank you), here is another one. But @Vor found an example of a deterministic CF language where the same construction would apply, if correct. This allowed identifying an error in the anchoring of the $y$ string in the application of the lemma. The lemma itself does not seem at fault. This is clearly too simplistic a construction. See more details in the comments.

After 2 failed attempts, that were disproved by @Hendrik Jan (thank you), here is another one, that is not more successful. @Vor found an example of a deterministic CF language where the same construction would apply, if correct. This allowed identifying an error in the anchoring of the $y$ string in the application of the lemma. The lemma itself does not seem at fault. This is clearly too simplistic a construction. See more details in the comments.

After 2 failed attempts, that were disproved by @Hendrik Jan (thank you), here is another one.

After 2 failed attempts, that were disproved by @Hendrik Jan (thank you), here is another one. But @Vor found an example of a deterministic CF language where the same construction would apply, if correct. This allowed identifying an error in the anchoring of the $y$ string in the application of the lemma. The lemma itself does not seem at fault. This is clearly too simplistic a construction. See more details in the comments.

We first try to use Ogden's lemma, which is like the pumping lemma, but applies to $p$ or more distinguished symbols that are marked on the string, $p$ being the pumping length for marked symbols (but we can pump more if we pump unmarked symbols). The pumping marked-length $p$ depends only on the language. This attempt will fail, but the failure will be a hint.

Proof: Similar to the proof of Ogden's lemma, but the subtrees corresponding to the strings $y$ and $xz$ are pruned so that they do not contain any path with twice the same non-terminal (except for the roots of these two subtrees). This necessarily limits the size of the generated strings $\hat x\hat z$ and $\hat y$ by a constant $q$. The strings $x^j$ and $z^j$, for $ j \geq 0$, corresponding to an unpruned version of the tree, are used mainly with $j=1$ to simplify the accounting.

I think that I shall never see
A string lovely as a tree.
For if it does not have a parse
The string is only a farce

We first try to use Ogden's lemma, which is like the pumping lemma, but applies to $p$ or more distinguished symbols that are marked on the string, $p$ being the pumping length for marked symbols (but the lemma can pump more because it can pump also unmarked symbols). The pumping marked-length $p$ depends only on the language. This attempt will fail, but the failure will be a hint.

Proof: Similar to the proof of Ogden's lemma, but the subtrees corresponding to the strings $y$ and $xz$ are pruned so that they do not contain any path with twice the same non-terminal (except for the roots of these two subtrees). This necessarily limits the size of the generated strings $\hat x\hat z$ and $\hat y$ by a constant $q$. The strings $x^j$ and $z^j$, for $ j \geq 0$, corresponding to an unpruned version of the tree, are used mainly with $j=1$ to simplify the accounting when the lemma is applied.

I think that I shall never see
A string lovely as a tree.
For if it does not have a parse,
The string is naught but a farce