Browse Prior Art Database

COMPARISONS BETWEEN SOME PUMPING CONDITIONS FOR CONTEXT-FREE LANGUAGES

IP.com Disclosure Number: IPCOM000148446D
Original Publication Date: 1985-Dec-31
Included in the Prior Art Database: 2007-Mar-30
Document File: 28 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Boonyavatana, R.: AUTHOR [+3]

Abstract

COMPARISONS BETWEEN SOME PUMPING CONDITI[ONS FOR CONTEXT-FREE LANGUAGES'

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 28

COMPARISONS BETWEEN SOME
PUMPING CONDITI[ONS FOR

CONTEXT-FREE LANGUAGES'

R. Boonyavzitana
G. Slutzki

December 1985

+ This report incorporates result of technical reports 85-12,13,17,25.

[This page contains 1 picture or other non-text object]

Page 2 of 28

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

[This page contains 1 picture or other non-text object]

Page 3 of 28

2

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