# Indexed Grammars—An Extension of Context-Free Grammars

@article{Aho1968IndexedGE, title={Indexed Grammars—An Extension of Context-Free Grammars}, author={Alfred V. Aho}, journal={Journal of the ACM (JACM)}, year={1968}, volume={15}, pages={647 - 671} }

A new type of grammar for generating formal languages, called an indexed grammar, is presented. An indexed grammar is an extension of a context-free grammar, and the class of languages generated by indexed grammars has closure properties and decidability results similar to those for context-free languages. The class of languages generated by indexed grammars properly includes all context-free languages and is a proper subset of the class of context-sensitive languages. Several subclasses of… Expand

#### Figures and Topics from this paper

#### 382 Citations

Context-free grammars on trees

- Computer Science, Mathematics
- STOC
- 1969

This paper defines the tree analogue of a non deterministic generalized sequential machine and obtain results about the domain and range of such a mapping and relates these results to the theory of generalized finite automata6. Expand

Context-Free Grammars with Storage

- Computer Science
- ArXiv
- 2014

The context-free S languages can be obtained from the deterministic one-way S automaton languages by way of the delta operations on languages, introduced in this paper. Expand

Controlled bidirectional grammars

- Mathematics, Computer Science
- 1988

We investigate context-free grammars the rules of which can be used in a productive and in a reductive fashion, while the application of these rules is controlled by a regular language. We… Expand

Boolean grammars

- Computer Science
- 2004

A new generalization of context-free grammars is introduced: Boolean grammars allow the use of all set-theoretic operations as an integral part of the formalism of rules. Rigorous semantics for these… Expand

Parsers for indexed grammars

- Computer Science
- International Journal of Computer & Information Sciences
- 2004

This work shows that the flag strings generated by indexed grammars are regular sets and can be generated by regular canonical systems, and generates all the deterministic contextfree languages, along with some noncontextfree languages. Expand

A Geometric Hierarchy Beyond Context-Free Languages

- Computer Science
- Theor. Comput. Sci.
- 1992

This paper gives a progression of automata and shows that it corresponds exactly to the language hierarchy defined with control grammars, the first member of which is context-free languages. Expand

Grammars, Derivation Modes and Properties of Indexed and Type-0 Languages

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1987

The context-free-like structure of the grammar is used as a tool to investigate normal-form transformations, Dyck languages and homomorphic characterizations and the two derivation modes yield the classes of indexed and type-0 languages respectively. Expand

On the Generative Power of Multiple Context-Free Grammars and Macro Grammars

- Computer Science
- IEICE Trans. Inf. Syst.
- 2008

The generative power of several subclasses of variable-linear macro Grammars and that of multiple context-free grammars are compared in details. Expand

The equivalence of four extensions of context-free grammars

- Computer Science
- Mathematical systems theory
- 2005

The result presented in this paper is that all four of the formalisms under consideration generate exactly the same class of string languages. Expand

A Generalization of Linear Indexed Grammars Equivalent to Simple Context-Free Tree Grammars

- Mathematics, Computer Science
- FG
- 2014

I define a generalization of linear indexed grammars that is equivalent to simple context-free tree grammars in the same way that linear indexed grammars are equivalent to tree-adjoining grammars.

#### References

SHOWING 1-10 OF 31 REFERENCES

Indexed Grammars-An Extension of Context Free Grammars

- Computer Science
- SWAT
- 1967

The class of indexed languages seems to be a closer approximation to theclass of algorithmic programming languages than either the class of context free languages or the classof context sensitive languages. Expand

Programmed Grammars: A New Device for Generating Formal Languages

- Mathematics, Computer Science
- SWAT
- 1967

The generative power of programmed grammars with various types of production cores is investigated, and every recursively enumerable language can be obtained from a cfpg language by a homomorphism. Expand

A New Normal-Form Theorem for Context-Free Phrase Structure Grammars

- Mathematics, Computer Science
- JACM
- 1965

It is given that every context-free phrase structure generator is strongly equivalent to one in standard form and offers an independent proo[' of a variant of the Chomsky-Setditzenberger 1tortoni form theorem. Expand

Abstract Families of Languages

- Computer Science
- SWAT
- 1967

The notion of an abstract family of languages (AFL) as a family of sets of words satisfying certain properties common to many types of formal languages is introduced. Operations preserving AFL are… Expand

On the nonexistence of a phrase structure grammar for ALGOL 60

- Computer Science
- CACM
- 1962

It is shown that no formal mechanisms of the type used are sufficient to define ALGOL 60. Expand

Stack automata and compiling

- Computer Science
- JACM
- 1967

A mathematical model is presented which embodies salient features of many modern compiling techniques, including deterministic linear bounded automaton and nondeterministic stack automaton, and particular instances of this more general device are noted. Expand

Nonerasing Stack Automata

- Computer Science
- J. Comput. Syst. Sci.
- 1967

It is shown that the Deterministic, nonerasing stack automaton is equivalent to a deterministic, off-line Turing machine whose storage tape never grows beyond n log"2n cells where n is the length of the input. Expand

One-way stack automata

- Mathematics, Computer Science
- JACM
- 1967

A number of operations which either preserve sets accepted by one-way stack automata or preserve sets accepted by deterministic one-way stack automata are presented. For example, sequential… Expand

Language and information

- Computer Science
- 1968

This book is a kind of precious book written by an experienced author and it will show you the reasonable reasons why you need to read this book. Expand

Computability and Unsolvability

- Mathematics, Computer Science
- McGraw-Hill Series in Information Processing and Computers
- 1958

Only for you today! Discover your favourite computability and unsolvability book right here by downloading and getting the soft file of the book. This is not your time to traditionally go to the book… Expand