Intercalation properties of context-free languages

dc.contributor.author	Boonyavatana, Rattikorn
dc.contributor.department	Computer Science
dc.date	2018-08-16T22:21:33.000
dc.date.accessioned	2020-07-02T06:05:02Z
dc.date.available	2020-07-02T06:05:02Z
dc.date.copyright	Wed Jan 01 00:00:00 UTC 1986
dc.date.issued	1986
dc.description.abstract	<p>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.</p>
dc.format.mimetype	application/pdf
dc.identifier	archive/lib.dr.iastate.edu/rtd/8142/
dc.identifier.articleid	9141
dc.identifier.contextkey	6329038
dc.identifier.doi	https://doi.org/10.31274/rtd-180813-6815
dc.identifier.s3bucket	isulib-bepress-aws-west
dc.identifier.submissionpath	rtd/8142
dc.identifier.uri	https://dr.lib.iastate.edu/handle/20.500.12876/81098
dc.language.iso	en
dc.source.bitstream	archive/lib.dr.iastate.edu/rtd/8142/r_8703689.pdf\|\|\|Sat Jan 15 02:07:07 UTC 2022
dc.subject.disciplines	Computer Sciences
dc.subject.keywords	Computer science
dc.title	Intercalation properties of context-free languages
dc.type	article
dc.type.genre	dissertation
dspace.entity.type	Publication
relation.isOrgUnitOfPublication	f7be4eb9-d1d0-4081-859b-b15cee251456
thesis.degree.level	dissertation
thesis.degree.name	Doctor of Philosophy

File

Original bundle

Now showing 1 - 1 of 1

Name:: r_8703689.pdf
Size:: 2.22 MB
Format:: Adobe Portable Document Format
Description:

Download

Collections

Theses and Dissertations