Browse Prior Art Database

COMPARISONS BETWEEN SOME PUMPING CONDITIONS FOR CONTEXT-FREE LANGUAGES+

IP.com Disclosure Number: IPCOM000128016D
Original Publication Date: 1985-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 25 page(s) / 57K

Publishing Venue

Software Patent Institute

Related People

R. Boonyavatana: AUTHOR [+4]

Abstract

Proving deeper properties of classes of languages is useful in at least two ways. First, our knowledge of the class in question has increased allowing deeper theoretical questions be asked and answered. The second benefit becomes substantial when the particular property is easily testable; it then becomes a convenient tool for proving that some languages are not in the class. Note that such properties provide necessary conditions which usually are not sufficient. Two such famous properties for the class of context-free languages are the ( classical ) pumping lemma of Bar-Hillel, Perles and Shamir [BPS] ( year 1961 ) and Parikh's theorem [P] ( year 1966 ). There is no doubt that, beyond the general importance of context-free languages, the popularity of the ( classical ) pumping lemma stems mainly from the simplicity of its formulation and the ease of its application. In 1968 Ogden [O] proved a considerably stronger pump-ing lemma for context-free languages; it has since then been named after its discoverer and is nowadays a standard and widely used tool for proving that given languages are not context-free. In 1976 Wise [W] has obtained a strong characterization of context-free languages which has a flavor of pumping. His characterizations provide necessary and sufficient conditions for context-freedom but may become rather unwieldy in applications. In this paper we will not be concerned with such strong conditions. In 1978 Sokolowski [S] proved another property of context-free languages which he showed to be applicable in some cases where the classical pumping lemma failed. In 1982 Grant [G] proved. an extension of the Sokolowski's criterion, Ni jholt [N] showed that it does not provide a sufficient condition and Bader and Moura [BM] proved a generalized Ogden's lemma by introducing the concept of excluded positions ( in addition to the distinguished positions in Ogden's lemma ). Bader and Moura showed. that their lemma is in fact stronger than Ogden's and that it does not provide a sufficient condition for context-freedom. Let us mention in passing that just a slightly weakened version of the main theorem of [BM] occurs already in the original paper of Sokolowski [S, lemma 2]. The classes of languages that satisfy the classical pumping conditions and the Ogden's conditions were studied by Horvath and Boasson [Ho, BH] in 1978. A pumping lemma for linear context-free languages is given in [B (proposition 6.6), HU(exercise 6.11)]. Ogden's lemma for linear languages was proved in [BS] ( as a special case of Ogden's lemma for nonterminal bounded languages ) and the general-ized Ogden's lemma is formulated in this paper. In this paper we will study the relationships between the various conditions mentioned above. In section 2 we present the basic definitions and some introductory results. In section 3 we begin the comparison between the general pumping conditions and the linear pumping conditions. Only the easier relevant results are given here. In section 4 we give several results related to the extended Sokolowski's condition of Grant [G]. We show that the generalized Ogden's lemma [BM] is stronger than Grant's condition ( implying that the latter condition :is not sufficient ) and we prove, using some number-theoretic arguments, that there are languages that satisfy Grant's condi-tion but not the classical pumping lemma. In section 5 we introduce two operations on languages and show their relevance to the classes of languages studied in this paper. The proofs of the three theorems in this section are given in the appendix. Sec-tion 6 is a short section which, using the results of section 5, completes the comparis-ons begun in section 4 between the Sokolowski-type conditions and the more stan-dard pumping conditions. In section 7, again using the technical results of section 5, we complete the story begun in section 3.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 9% of the total text.

Page 1 of 25

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

COMPARISONS BETWEEN SOME PUMPING CONDITIONS FOR CONTEXT-FREE LANGUAGES+

R. Boonyavatana G. Slutzki

TR#85-32 December 1985 + This report incorporates result of technical reports 85-12,13,17,25.

1 INTRODUCTION.

Proving deeper properties of classes of languages is useful in at least two ways. First, our knowledge of the class in question has increased allowing deeper theoretical questions be asked and answered. The second benefit becomes substantial when the particular property is easily testable; it then becomes a convenient tool for proving that some languages are not in the class. Note that such properties provide necessary conditions which usually are not sufficient. Two such famous properties for the class of context-free languages are the ( classical ) pumping lemma of Bar-Hillel, Perles and Shamir [BPS] ( year 1961 ) and Parikh's theorem [P] ( year 1966 ). There is no doubt that, beyond the general importance of context-free languages, the popularity of the ( classical ) pumping lemma stems mainly from the simplicity of its formulation and the ease of its application. In 1968 Ogden [O] proved a considerably stronger pump-ing lemma for context-free languages; it has since then been named after its discoverer and is nowadays a standard and widely used tool for proving that given languages are not context-free. In 1976 Wise [W] has obtained a strong characterization of context-free languages which has a flavor of pumping. His characterizations provide necessary and sufficient conditions for context-freedom but may become rather unwieldy in applications. In this paper we will not be concerned with such strong conditions. In 1978 Sokolowski [S] proved another property of context-free languages which he showed to be applicable in some cases where the classical pumping lemma failed. In 1982 Grant [G] proved. an extension of the Sokolowski's criterion, Ni jholt [N] showed that it does not provide a sufficient condition and Bader and Moura [BM] proved a generalized Ogden's lemma by introducing the concept of excluded positions ( in addition to the distinguished positions in Ogden's lemma ). Bader and Moura showed. that their lemma is in fact stronger than Ogden's and that it does not provide a sufficient condition for context- freedom. Let us mention in passing that just a slightly weakened version of the main theorem of [BM] occurs already in the original paper of Sokolowski [S, lemma 2]. The classes of languages that satisfy the classical pumping conditions and the Ogden's conditions were studied by Horvath and Boasson [Ho, BH] in 1978. A pumping lemma for linear context-free languages is given in [B (proposition 6.6), HU(exercise 6.11)]. Ogden's lemma for linear languages was proved in [BS] ( as a special case of Ogden's lemma for nonterminal bounded languages ) and the general-ized Ogden's lemma is formulated in this paper. In this paper we will study the relationship...