Direction controlled programmed grammars | Acta Informatica Skip to main content
Springer Nature Link
Log in

Direction controlled programmed grammars

  • Published:
Acta Informatica Aims and scope Submit manuscript

Summary

A generalization of the notion of a context-free grammar is presented here. It is based on the notion of a programmed grammar. When the underlying context-free rules do not contain erasing, the class of languages obtained is identical with the class of context-sensitive languages. With underlying context-free rules containing erasing one obtains the class of recursively enumerable languages.

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
¥17,985 /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 includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Abraham, S.: Some questions of phrase structure grammars. Computational Linguistics 4 (1965).

  2. Aho, A. V.: Indexed grammars- an extension of context-free grammars. Journal of the A.C.M. 15, No. 4, Oct. (1968).

  3. Greibach, S., Hopcroft, J.: Scattered context grammars. Journal of Computer and System Sciences, 3 (1969).

  4. Hopcroft, J., Ullman, J.: Formal languages and their relation to automata. Addison-Wesley Publ. Comp. 1969.

  5. Rosenkrantz, D.: Programmed grammars and classes of formal languages. Journal of the A.C.M. 16, No. 1 (1969).

    Google Scholar 

  6. Rozenberg, G.: On the introduction of orderings into the grammars of Chomsky's hierarchy. Bulletin de l'Académie Polonaise des Sciences 17, No. 9 (1969).

  7. Stotsky, E.: Some restrictions on derivations in context-sensitive grammars. Russian Acad. of Sciences N.T.I, s. 2. 7 (1967) [in Russian].

Download references

Author information

Authors and Affiliations

  1. Mathematical Institute R. University Utrecht Utrecht-Uithof, 6, Budapestlaan, The Netherlands

    G. Rozenberg

Authors
  1. G. Rozenberg
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

The author is indebted to Drs. T. A. Zoethout for very useful discussions concerning this paper.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Rozenberg, G. Direction controlled programmed grammars. Acta Informatica 1, 242–252 (1972). https://doi.org/10.1007/BF00288688

Download citation

  • Received:

  • Issue Date:

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

Keywords

Search

Navigation