On the structure of context-sensitive grammars | Zendy

Ronald V. Book | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On the structure of context-sensitive grammars

Author(s) -

Ronald V. Book

Publication year - 1973

Publication title -

international journal of computer and information sciences

Language(s) - English

Resource type - Journals

ISSN - 0091-7036

DOI - 10.1007/bf00976059

Subject(s) - context sensitive grammar , tree adjoining grammar , context free grammar , undecidable problem , rule based machine translation , generative grammar , context (archaeology) , computer science , grammar , extended affix grammar , embedded pushdown automaton , phrase structure grammar , programming language , l attributed grammar , natural language processing , linguistics , artificial intelligence , theoretical computer science , philosophy , geography , decidability , archaeology

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?

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research