Talk:Pumping lemma for context-free languages

Proof?

Can someone add the proof for this lemma similar to the proof of the pumping lemma for regular languages please. — Preceding unsigned comment added by 2A02:1811:2C2D:2100:8D97:7F0:3300:95A (talk) 16:41, 5 January 2021 (UTC)

Finite languages cannot be pumped

Regarding the edit recently made eliminating infinite L as a condition for the pumping lemma... I realize most statements of the pumping lemmas for CFL and regular sets are sloppy and eliminate this condition, but it is required. Any finite language is trivially regular and hence context free. The pumping lemma for CFL requires that |vy| >= 1. Thus, the pumping operation creates strings of unbounded length. Hence, L must be infinite. Vantelimus (talk) 18:42, 5 March 2008 (UTC)

On revisiting this issue, I have retracted my edit. What I said is correct, but what the previous editor said was also correct. Parsimony favors his statement.Vantelimus (talk) 11:13, 30 March 2008 (UTC)

Sufficient?

This may be a dumb question, but is the pumping lemma for context-free languages sufficient, that is, is every language for which the pumping lemma for CFL holds a CFL? —Preceding unsigned comment added by Subwy (talk • contribs) 16:11, 10 June 2009 (UTC)

• The Pumping Lemma is a necessary, but not sufficient, condition. Vantelimus (talk) 19:51, 10 June 2009 (UTC)
• Is there a known necessary and sufficient condition for context-free languages, like Myhill–Nerode theorem for regular languages? — Preceding unsigned comment added by 202.89.176.30 (talk) 12:16, 17 August 2011 (UTC)

Formal Definition

I suggest to include a formal definition for clarity: $\forall L\in CFL.\;\exists p\in \mathbf {N} ^{+}.\;\forall s\in L.\;|s|\geq p\rightarrow (\exists u,v,x,y,z.\;s=uvxyz\;\wedge \;|vxy|\leq p\;\wedge \;|vy|\geq 1\;\wedge \;(\forall n\in \mathbf {N} \cup \{0\}.uv^{n}xy^{n}z\in L))$

This is not any clearer than stating the pumping lemma in natural language. Vstephen B (talk) 16:09, 1 May 2023 (UTC)