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

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...