Abstract
Divide the context-free languages into equivalence classes in the following way: L1 and L2 are in the same class if there are a-transducers M and such that M(L1) = L2 and . Define L1 and L2 to be structurally similar if they are in the same class. Among the results given below are: 1) if L1 and L2 are structurally similar and L1 has a structurally similar set of (right) sentential forms then so does L2, 2) if L1 and L2 are structurally similar and L1 is deterministic then L2 has a structurally similar set of right sentential forms, 3) if L1 and L2 are structurally similar and L1 is a parenthesis language then L2 has a structurally similar set of sentential forms, 4) there is a nonempty equivalence class of structurally similar languages that contains no (right) sentential forms of any grammar, 5) if an equivalence class contains any set of (right) sentential forms at all then every language in the class has a set of (right) sentential forms in that class.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cohen, R.S., K. Culik II, LR-regular grammar — an extension of LR(k) grammars, IEEE Conference Record of 12th Symposium on Switching and Automata Theory (1971), 153–165.
DeRemer, F.L., Simple LR(k) grammars, CACM 14 (1971), 453–460.
Elgot, C.C., J.E. Mezei, On relations defined by generalized finite automata, IBM J.Res. and Dev. 9 (1965), 47–68.
Ginsburg, S., S. Griebach, J. Hoperoft, Studies in abstract families of languages, Memoirs of the AMS 87,(1969).
Greibach, S.A., The unsolvability of the recognition of linear context-free languages, J.Assoc.Comp.Mach. 13 (1966), 582–587.
Gray, J., M. Harrison, Coverings and reduction problems for context-free grammars, J.Assoc.Comp.Mach. 19 (1972), 675–698.
Knuth, D., On translation of languages from left to right, Information and Control 8 (1965), 607–639.
Lindenmayer, A., Mathematical models for cellular interaction in development I, II, J.Theoret.Biol. 18 (1968), 280–315.
Lindenmayer, A., Development systems with interactions, their languages and grammars, J.Theoret.Biol. 30 (1971), 455–484.
McNaughton, R., Parenthesis grammars, J.Assoc.Comp.Mach. 14 (1967), 490–500.
Paz, A., A. Salomaa, Integral sequential word functions and growth equivalence of Lindenmayer systems, Information and Control 23 (1973), 313–343.
Rozenberg, G., P.G. Doucet, On OL-languages, Information and Control 19 (1971), 302–318.
Salomaa, A., Sentential forms of context-free grammars, Acta Informatica 2 (1974), 40–49.
Williams, J.H., Bounded context parsable grammars, Technical Report #58, Computer Science Department, Univ. of Wisc., Madison, Wisc. (1969).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1974 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Blattner, M. (1974). Transductions of Context-Free Languages into Sets of Sentential Forms. In: Loeckx, J. (eds) Automata, Languages and Programming. ICALP 1974. Lecture Notes in Computer Science, vol 14. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-21545-6_39
Download citation
DOI: https://doi.org/10.1007/978-3-662-21545-6_39
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-06841-9
Online ISBN: 978-3-662-21545-6
eBook Packages: Springer Book Archive