×

zbMATH — the first resource for mathematics

Control sets on grammars. (English) Zbl 0157.33604
Let \(G\) be a phrase structure grammar and \(C\) a set of sequences of rules of \(G\). \(L_t(G)\) consists of those words generated by leftmost derivations of \(G\) whose corresponding sequence of rules is in \(C\). The following result is typical:
Theorem. If \(G\) is an arbitrary phrase structure grammar, \(L_t(G)\) is an abstract family of languages (AFL) if \(C\) is.
Corollary. If \(C\) is regular then \(L_t(G)\) is context free.
Corollary. For each recursively enumerable set \(R\) there exists a context free grammar \(G\) and a context tree language \(C\) so that \(L_t(G)=R\).
Reviewer: M. A. Harrison

MSC:
03D05 Automata and formal grammars in connection with logical questions
68Q42 Grammars and rewriting systems
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Y. Bar-Hillel, M. Perles andE. Shamir, On formal properties of simple phrase structure grammars,Z. Phonetik Sprachwiss. Kommunikat. 14 (1961), 143–172. · Zbl 0106.34501
[2] N. Chomsky, Three models for the description of language,IRE Trans. Information Theory IT2 (1956), 113–124. · Zbl 0156.25401 · doi:10.1109/TIT.1956.1056813
[3] N. Chomsky, On certain formal properties of grammars,Information and Control 2 (1959), 137–167. · Zbl 0088.10801 · doi:10.1016/S0019-9958(59)90362-6
[4] J. Evey, ”The theory and application of pushdown store machines”, Mathematical Linguistics and Automatic Translation, Report No. NSF-10, The Computation Laboratory of Harvard University, 1963. · Zbl 0196.52501
[5] S. Ginsburg andS. Greibach, Mappings which preserve context-sensitive languages,Information and Control 9 (1966), 563–582. · Zbl 0145.00803 · doi:10.1016/S0019-9958(66)80016-5
[6] S. Ginsburg andS. Greibach, ”Abstract families of languages”, SDC Report No. TM-738/031/00, 17 April 1967. · Zbl 0194.31402
[7] S. Ginsburg, S. Greibach andM. Harrison, One-way stack automata,J. Assoc. Comput. Mach. 14 (1967), 389–418. · Zbl 0171.14803
[8] S. Ginsburg andG. F. Rose, Preservation of languages by transducers,Information and Control 9 (1966), 153–176. · Zbl 0186.01301 · doi:10.1016/S0019-9958(66)90211-7
[9] S. Ginsburg andE. H. Spanier, BoundedAlgol-like languages,Trans. Amer. Math. Soc. 113 (1964), 333–368. · Zbl 0142.24803
[10] S. Greibach, A new normal-form theorem for context-free phrase structure grammars,J. Assoc. Comput. Mach. 12 (1965), 42–52. · Zbl 0135.18404
[11] S. Greibach andJ. Hopcroft, ”Independence of AFL operations”, SDC Report No. TM-738/034/00, 12 July 1967.
[12] G. H. Matthews, A note on asymmetry in phrase structure grammars,Information and Control 7 (1964), 360–365. · Zbl 0134.24603 · doi:10.1016/S0019-9958(64)90406-1
[13] G. H. Matthews, Two-way languages,Information and Control 10 (1967), 111–119. · Zbl 0153.01001 · doi:10.1016/S0019-9958(67)80001-9
[14] M. Rabin andD. Scott, Finite automata and their decision problems,IBM J. Res. Develop. 3 (1959), 114–125. · Zbl 0158.25404 · doi:10.1147/rd.32.0114
[15] D. Rosenkrantz, ”Programmed grammars–a new device for generating formal languages”, Ph.D. Thesis, Columbia University, 1967.
[16] S. Scheinberg, Note on the Boolean properties of context-free languages,Information and Control 3 (1960), 372–375. · Zbl 0096.34706 · doi:10.1016/S0019-9958(60)90965-7
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.