Indexed language

From Infogalactic: the planetary knowledge core
Jump to: navigation, search

Indexed languages are a class of formal languages discovered by Alfred Aho;[1] they are described by indexed grammars and can be recognized by nested stack automata.[2]

Indexed languages are a proper subset of context-sensitive languages.[1] They qualify as an abstract family of languages (furthermore a full AFL) and hence satisfy many closure properties. However, they are not closed under intersection or complement.[1]

The class of indexed languages has practical importance in natural language processing as a computationally affordable[citation needed] generalization of context-free languages, since indexed grammars can describe many of the nonlocal constraints occurring in natural languages.

Gerald Gazdar (1988)[3] and Vijay-Shanker (1987)[4] introduced a mildly context-sensitive language class now known as linear indexed grammars (LIG).[5] Linear indexed grammars have additional restrictions relative to IG. LIGs are weakly equivalent (generate the same language class) as tree adjoining grammars.[6]


The following languages are indexed, but are not context-free:

 \{a^n b^n c^n d^n| n \geq 1 \} [3]
 \{a^n b^m c^n d^m | m,n \geq 0 \} [2]

These two languages are also indexed, but are not even mildly context sensitive under Gazdar's characterization:

 \{a^{2^{n}} | n \geq 0 \} [2]
 \{www | w \in \{a,b\}^+ \} [3]

On the other hand, the following language is not indexed:[7]

\{(a b^n)^n | n \geq 0 \}


Hopcroft and Ullman tend to consider indexed languages as a "natural" class, since they are generated by several formalisms, such as:[9]

Hayashi[14] generalized the pumping lemma to indexed grammars. Conversely, Gilman[7][15] gives a "shrinking lemma" for indexed languages.

See also


  1. 1.0 1.1 1.2 1.3 Aho, Alfred (1968). "Indexed grammars—an extension of context-free grammars". Journal of the ACM. 15 (4): 647–671. doi:10.1145/321479.321488.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
  2. 2.0 2.1 2.2 Partee, Barbara; Alice ter Meulen; Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers. pp. 536–542. ISBN 978-90-277-2245-4.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
  3. 3.0 3.1 3.2 Gazdar, Gerald (1988). "Applicability of Indexed Grammars to Natural Languages". In U. Reyle and C. Rohrer (ed.). Natural Language Parsing and Linguistic Theories. pp. 69–94.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
  5. Laura Kallmeyer (2010). Parsing Beyond Context-Free Grammars. Springer Science & Business Media. p. 31. ISBN 978-3-642-14846-0.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
  6. Laura Kallmeyer (16 August 2010). Parsing Beyond Context-Free Grammars. Springer Science & Business Media. p. 32. ISBN 978-3-642-14846-0.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
  7. 7.0 7.1 Gilman, Robert H. (1996). "A Shrinking Lemma for Indexed Languages" (PDF). Theoretical Computer Science. 163 (1–2): 277–281. doi:10.1016/0304-3975(96)00244-7.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
  8. Hopcroft, John; Jeffrey Ullman (1979). Introduction to automata theory, languages, and computation. Addison-Wesley. p. 390. ISBN 0-201-02988-X.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
  9. Introduction to automata theory, languages, and computation,[8]Bibliographic notes, p.394-395
  10. Alfred Aho (1969). "Nested Stack Automata". Journal of the ACM. 16 (3): 383–406. doi:10.1145/321526.321529.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
  11. Michael J. Fischer (1968). "Grammars with Macro-Like Productions". Proc. 9th Ann. IEEE Symp. on Switching and Automata Theory (SWAT). pp. 131–142.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
  12. Sheila A. Greibach (1970). "Full AFL's and Nested Iterated Substitution" (PDF). Information and Control. 16 (1): 7–35. doi:10.1016/s0019-9958(70)80039-0.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
  13. T.S.E. Maibaum (1974). "A Generalized Approach to Formal Languages" (PDF). J. Computer and System Sciences. 8 (3): 409–439. doi:10.1016/s0022-0000(74)80031-0.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
  14. T. Hayashi (1973). "On Derivation Trees of Indexed Grammars - An Extension of the uvxyz Theorem". Publication of the Research Institute for Mathematical Sciences. Research Institute for Mathematical Sciences. 9 (1): 61–92. doi:10.2977/prims/1195192738.<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>
  15. Robert H. Gilman (Sep 1995). "A Shrinking Lemma for Indexed Languages". Cite journal requires |journal= (help)<templatestyles src="Module:Citation/CS1/styles.css"></templatestyles>

External links