Intercalation properties of context-free languages

Thumbnail Image
Date
1986
Authors
Boonyavatana, Rattikorn
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Abstract

Context-freedom of a language implies certain intercalation properties known as pumping or iteration lemmas. Although the question of a converse result for some of the properties has been studied, it is still not entirely clear how these properties are related, which are the stronger ones and which are weaker;Among the intercalation properties for context-free languages the better known are the general pumping conditions (generalized Ogden's, Ogden's and classic pumping conditions), Sokolowski-type conditions (Sokolowski's and Extended Sokolowski's conditions) and the Interchange condition. We present a rather systematic investigation of the relationships among these properties; it turns out that the three types of properties, namely pumping, Sokolowski-type and interchange, above are independent. However, the interchange condition is strictly stronger than the Sokolowski's condition;Intercalation properties of some subclasses of context-free languages are also studied. We prove a pumping lemma and an Ogden's lemma for nonterminal bounded languages and show that none of these two conditions is sufficient. We also investigate three of Igarashi's pumping conditions for real-time deterministic context-free languages and show that these conditions are not sufficient either. Furthermore, we formulate linear analogues of the general pumping and interchange conditions and then compare them to the general context-free case. The results show that these conditions are also independent.

Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
article
Comments
Rights Statement
Copyright
Wed Jan 01 00:00:00 UTC 1986
Funding
Subject Categories
Supplemental Resources
Source