Degree Type

Dissertation

Date of Award

1986

Degree Name

Doctor of Philosophy

Department

Computer Science

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.

DOI

https://doi.org/10.31274/rtd-180813-6815

Publisher

Digital Repository @ Iowa State University, http://lib.dr.iastate.edu/

Copyright Owner

Rattikorn Boonyavatana

Language

en

Proquest ID

AAI8703689

File Format

application/pdf

File Size

103 pages

Share

COinS