Talk:Pumping lemma for context-free languages

Latest comment: 1 year ago by Vstephen B in topic Formal Definition

Proof?

edit

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)Reply

Finite languages cannot be pumped

edit

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)Reply

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)Reply

Sufficient?

edit

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 (talkcontribs) 16:11, 10 June 2009 (UTC)Reply

Formal Definition

edit

I suggest to include a formal definition for clarity:  

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