Comparisons between some pumping conditions for context-free languages

R. Hewett, G. Slutzki

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

We present a systematic investigation of the relationships between various pumping properties-the classic pumping condition of Bar-Hillel et al., Ogden's condition, a generalized Ogden condition of Bader and Moura, Sokolowski's condition, an extended Sokolowski condition of Grant, and linear versions of some of these conditions. We define special language operations that allow us to produce, in a systematical and uniform way, languages that satisfy some combinations of the pumping conditions but not the others. We show, among others, that the general and the linear pumping conditions are "orthogonal," whereas the generalized Ogden condition is stronger than the extended Sokolowski condition.

Original languageEnglish
Pages (from-to)223-233
Number of pages11
JournalMathematical Systems Theory
Volume21
Issue number1
DOIs
StatePublished - Dec 1988

Fingerprint Dive into the research topics of 'Comparisons between some pumping conditions for context-free languages'. Together they form a unique fingerprint.

Cite this