iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://unpaywall.org/10.1007/BF00976059
On the structure of context-sensitive grammars | International Journal of Parallel Programming Skip to main content
Springer Nature Link
Log in

On the structure of context-sensitive grammars

  • Published:
International Journal of Computer & Information Sciences Aims and scope Submit manuscript

Abstract

It is well known that the family of context-sensitive grammars generate languages which are not context-free and that it is undecidable whether a context-sensitive grammar generates a context-free language. However, the mechanism by which the use of context allows a non-context-free language to be generated is not well understood. In this paper we attempt to focus on this problem by surveying some of the results which speak to two questions: (i) What constraints can be placed on the form of the rules of context-sensitive grammars without restricting the weak generative capacity? (ii) What (nontrivial) constraints can be placed on the form of the rules of context-sensitive grammars such that only context-free languages will be generated?

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. S. Abraham, “Some questions of phrase-structure grammars,”Comp. Linguistics 4:61–70 (1965).

    Google Scholar 

  2. B. Baker, “Arbitrary grammars generating context-free languages,”Info. and Control, to appear.

  3. D. Benson, “Syntax and semantics: a categorical view,”Info. and Control 17:145–160 (1970).

    Google Scholar 

  4. R. Book, “Time-bounded grammars and their languages,”J. Computer and System Sci. 5:397–429 (1971).

    Google Scholar 

  5. R. Book, “Terminal context in context-sensitive grammars,”SIAM J. Computing 1:20–30 (1972).

    Google Scholar 

  6. N. Chomsky, “Formal properties of grammars,” inHandbook of Mathematical Psychology, Vol. II, R. D. Luce, Bush, and Galanter, Eds. (Wiley, New York, 1963).

    Google Scholar 

  7. R. Evey, “The theory and application of pushdown store machines,” Ph.D. Dissertation, Harvard Univ., 1963; appears as “Math. Linguistics and Automatic Translation,” NSF-10 (1963), Computation Lab., Harvard Univ., Cambridge, Mass.

  8. S. Ginsburg,The Mathematical Theory of Context-Free Languages (McGraw-Hill, New York, 1966).

    Google Scholar 

  9. S. Ginsburg and S. A. Greibach, “Mappings which preserve context-sensitive languages,”Info. and Control 9:563–582 (1966).

    Google Scholar 

  10. S. Ginsburg and S. A. Greibach, “Abstract families of languages,”Memoir, Am. Math. Soc. 87:1–32 (1969).

    Google Scholar 

  11. A. Gladkii, “Grammars with linear memory” (in Russian),Algebri i Logika Sem. 2:43–55 (1963).

    Google Scholar 

  12. A. Gladkii, “On the complexity of derivations in phrase-structure grammars” (in Russian),Algebri i Logika Sem. 3:29–44 (1964).

    Google Scholar 

  13. T. Griffiths, “Some remarks on derivations in general rewriting systems,”Info. and Control 12:27–54 (1968).

    Google Scholar 

  14. L. Haines, “Representation theorems for context-sensitive languages,” unpublished manuscript.

  15. M. Harrison, “On the relation between grammars and automata,” inInformation Systems Science, Vol. 4, J. Tou, Ed. (Plenum, New York, 1972), pp. 39–92.

    Google Scholar 

  16. M. Harrison and M. Schkolnick, “A grammatical characterization of one-way nondeterministic stack languages,”J. ACM 18:148–172 (1971).

    Google Scholar 

  17. T. Hibbard, “Scan-limited automata and context-limited grammars,” Ph.D. Dissertation, Univ. of California, Los Angeles, 1966.

    Google Scholar 

  18. S.-Y. Kuroda, “Classes of languages and linear-bounded automata,”Info. and Control 7:207–223 (1964).

    Google Scholar 

  19. G. H. Matthews, “A note on asymmetry in phrase-structure grammars,”Info. and Control 7:360–365 (1964).

    Google Scholar 

  20. G. H. Matthews, “Two-way languages,”Info. and Control 10:111–119 (1967).

    Google Scholar 

  21. D. Rosenkrantz, “Programmed grammars and classes of formal languages,”J. ACM 16:107–131 (1969).

    Google Scholar 

  22. A. Salomaa, “On grammars with restricted use of productions,”Ann. Acad. Sci. Fenn., Ser. A 1969, No. 454.

  23. A. Salomaa, “On some families of formal languages obtained by regulated derivations,”Ann. Acad. Sci. Fenn., Ser. A 1970, No. 479.

  24. W. Savitch, “Normal form theorems for phrase structure grammars,” Presented atSixth Princeton Conf. on Info. Sci. and Systems, 1972.

  25. W. Sillars, “Formal properties of essentially context-dependent languages,” Ph.D. Dissertation, Pennsylvania State Univ., 1968.

  26. J. Thatcher, “Characterizing derivation trees of context-free grammars through a generalization of finite automata theory,”J. Computer and System Sci. 1:317–322 (1967).

    Google Scholar 

  27. B. Wegbreit, “A generator of context-sensitive languages,”J. Computer and System Sci. 3:456–461 (1969).

    Google Scholar 

  28. A. Aho, “Indexed grammars—An extension of context-free grammars,”J. ACM 15:647–671 (1968).

    Google Scholar 

  29. M. Fischer, “Grammars with macrolike productions,” Ph.D. Dissertation, Harvard Univ., Cambridge, Massachusetts, 1968.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Center for Research in Computing Technology, Harvard University, Cambridge, Massachusetts

    Ronald V. Book

Authors
  1. Ronald V. Book
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

The preparation of this paper was supported in part by the National Science Foundation under Grants NSF-GJ-30409 and GS-803, by the National Aeronautics and Space Administration under Grant NGR-22-007-176, and by the 1972 Advanced Research Workshop on Tree Mappings, MSSB, Center for Advanced Study in the Behavioral Sciences.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Book, R.V. On the structure of context-sensitive grammars. International Journal of Computer and Information Sciences 2, 129–139 (1973). https://doi.org/10.1007/BF00976059

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00976059

Keywords

Search

Navigation