Talk:Pumping lemma for context-free languages

From Wikipedia, the free encyclopedia

	Philosophy Portal This article is within the scope of the WikiProject Philosophy, which collaborates on articles related to philosophy. To participate, you can edit this article or visit the project page for more details.
???	This article has not yet received a rating on the quality scale.
???	This article has not yet received an importance rating on the importance scale.
Additional information: Related task forces (core areas): Logic

[edit] 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)