COMPARISONS BETWEEN SOME PUMPING CONDITIONS FOR CONTEXT-FREE LANGUAGES
Original Publication Date: 1985-Dec-31
Included in the Prior Art Database: 2007-Mar-30
Software Patent Institute
Boonyavatana, R.: AUTHOR [+3]
COMPARISONS BETWEEN SOME PUMPING CONDITI[ONS FOR CONTEXT-FREE LANGUAGES'
COMPARISONS BETWEEN SOME
PUMPING CONDITI[ONS FOR
+ This report incorporates result of technical reports 85-12,13,17,25.
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 homes 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 [PI ( year 1966 1. 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 discoveser and is nowadays a standard and widely used tcml 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 [GI proved an extension of the Sokolowski's criterion, Nijholt [N]
showed that it does not provide a sufficient condition and Bader and Mourn [BM] proved a generalized Ogden's lemma by introdlucing the concept of excluded positions
( in addition to the distinguished positions in Ogden's lemma 1. Bader and Moura showed that their lemma is in fact stronger than Ogden's and that it does not provide a suf6cimt 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 21. 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.1 I)]. Ogden's lemma for linear languages was proved in [...