noe@sunc1.cs.uiuc.edu (Roger Noe) (05/31/91)
Follow-ups redirected to comp.theory. In article <1544@cvbnetPrime.COM> dwilson@cvbnet.prime.com (David Wilson {x6203}) writes: > The pumping lemma for regular languages states... > R(L) implies P(L), where > R(L) means L is a regular language > P(L) means L is a pumpable language,.... > Does P(L) also imply R(L)? In other words, are there nonregular > languages which are nonetheless pumpable? P(L) is a necessary but not sufficient condition for regular languages. By way of example, let L = (L1 Union L2) over SIGMA = { a, b } where: L1 = { a^j b^k a^k : j >= 1 and k >= 0 } L2 = the set denoted by the regular expression b*a* L is clearly not regular, yet it satisfies the pumping lemma condition P(L). There are stronger versions of the traditional pumping lemma for regular languages. For example, if L is regular, then there exists n such that for any z in L with |z| >= n, EVERY substring of z of length n can be decomposed into uvw with v pumpable. I don't think this version is strong enough to be necessary and sufficient, but I'm pretty sure such conditions exist. For more details, see any good text in the field, such as Hopcroft and Ullman's "Intro. to Automata Theory, Languages, and Computation." -- Roger Noe roger-noe@uiuc.edu Department of Computer Science noe@cs.uiuc.edu University of Illinois 40:06:39 N. 88:13:41 W. Urbana, IL 61801 USA