Abstract
A functionf on the non-negative integers is a context-free preserving function (cfpf) if and only if for every context-free languageL, {x|(∃y) (xy ∈ L, and |y| =f(|x|))} is a context-free language. In this note we give an algebraic characterization of the class of cfpf's.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
S. Ginsburg,The Mathematical Theory of Context-free Languages, McGraw-Hill Book Co., 1966.
J. E. Hopcroft andJ. D. Ullman,Formal Languages and Their Relation to Automata, Addison-Wesley Publishing Co., 1969.
S. R. Kosaraju, Finite state automata with markers,Proc. Fourth Annual Princeton Conference on Information Sciences and Systems, 1970, p. 380.
S. R. Kosaraju, Regularity preserving functions, Tech. Report, JHU-EE 74-2, Johns Hopkins University, Electrical Engineering Dept., January 1974.
R. McNaughton, Personal Communication.
D. von Siefkes, Decidable extensions of monadic second order successor arithmetic, InAutomatentheorie und formale Sprachen, Bericht Tagung Oberwolfach Okt. 1969 (ed. J. Dorr and G. Hotz) Mannheim 1970, pp. 441–472.
J. I. Seiferas, A note on prefixes of regular languages,ACM SIGACT News, January 1974, pp. 25–29.
R. E. Stearns andJ. Hartmanis, Regularity preserving modifications of regular expressions,Information and Control, 1963, pp. 55–69.
Author information
Authors and Affiliations
Additional information
This research was supported by the National Bureau of Standards under Contract 3-35999.
Rights and permissions
About this article
Cite this article
Kosaraju, S.R. Context-free preserving functions. Math. Systems Theory 9, 193–197 (1975). https://doi.org/10.1007/BF01704019
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01704019