Intercalation properties of context-free languages Boonyavatana, Rattikorn
dc.contributor.department Computer Science 2018-08-16T22:21:33.000 2020-07-02T06:05:02Z 2020-07-02T06:05:02Z Wed Jan 01 00:00:00 UTC 1986 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/
dc.identifier.articleid 9141
dc.identifier.contextkey 6329038
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath rtd/8142
dc.language.iso en
dc.source.bitstream archive/|||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 dissertation Doctor of Philosophy
Original bundle
Now showing 1 - 1 of 1
2.22 MB
Adobe Portable Document Format