Reference. Indexed grammars—an extension of context-free grammars
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 indexed grammars generate interesting classes of languages.
Cite
Cites 14 works (1 here)
External (13)
- Nested stack automata (Aho; cited as submitted, later JACM 1969) (1969)
- Stack automata and compiling (1967)
- One-way stack automata (1967)
- Nonerasing stack automata (1967)
- Abstract families of languages (1967)
- Programmed grammars – a new device for generating formal languages (1967)
- The Mathematical Theory of Context Free Languages (1966)
- A New Normal-Form Theorem for Context-Free Phrase Structure Grammars (1965)
- On the computational complexity of algorithms (1965)
- Classes of languages and linear-bounded automata (1964)
- On the nonexistence of a phrase structure grammar for ALGOL 60 (1962)
- On formal properties of simple phrase structure grammars (1961)
- Computability and Unsolvability (1958)