Abstract
We study languages which can be described as limits of fast converging infinite sequences of context-free languages. Such a sequence \(L_0 \subseteq L_1 \subseteq L_2 \subseteq\) ... is fast converging if each string w of its limit language belongs to an Li which has a grammatical description very concise in comparison with the length of w . We prove that these languages are closely related to context-free languages in several properties: pumping lemma, interchange lemma, regularity of unary languages, full AFL properties. The languages can differ, however, in their computational complexity: we construct languages of arbitrarily high complexity, even languages which are not recursively enumerable, but have fast context-free approximations.
Preview
Unable to display preview. Download preview PDF.
References
Brandenburg F. J., On one-way auxiliary pushdown automata, Proc. of 3rd GI Conf. Theor. Comp. Science, LNCS 48 (1977)
Chytil M. P., Wagner K., Separation results for low nondeterministic auxiliary pushdown space complexity classes, manuscript, 1984
Chytil M. P, Almost context-free languages, to appear in Fundamenta Mathematicae, Dec. 1986
Hoperoft J. E., Ullman J. D., Formal languages and their relation to automata, Addison-Wesley 1969
Knuth D. E., Semantics of context-free languages, Math. System Theory 2 (1978)
Correction: Math. Sytem Theory 5 (1978)
Ogden W., Ross R. J., Winklmann K., An "Interchange Lemma" for context-free languages, SIAM J. Comput., Vol. 14, No 2, May 1985
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1986 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chytil, M.P. (1986). Kins of context-free languages. In: Gruska, J., Rovan, B., Wiedermann, J. (eds) Mathematical Foundations of Computer Science 1986. MFCS 1986. Lecture Notes in Computer Science, vol 233. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0016233
Download citation
DOI: https://doi.org/10.1007/BFb0016233
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-16783-9
Online ISBN: 978-3-540-39909-4
eBook Packages: Springer Book Archive