Indexed languages are a proper subset of context-sensitive languages. 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. Gerald Gazdar has characterized the mildly context-sensitive languages in terms of linear indexed grammars.
The class of indexed languages has practical importance in natural language processing as a computationally affordable generalization of context-free languages, since indexed grammars can describe many of the nonlocal constraints occurring in natural languages.
The following languages are indexed, but are not context-free:
These two languages are also indexed, but are not even mildly context sensitive under Gazdar's characterization:
On the other hand, the following language is not indexed:
- Aho, Alfred (1968). "Indexed grammars—an extension of context-free grammars". Journal of the ACM 15 (4): 647–671. doi:10.1145/321479.321488.
- Partee, Barbara; Alice ter Meulen, and Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers. pp. 536–542. ISBN 978-90-277-2245-4.
- Gazdar, Gerald (1988). "Applicability of Indexed Grammars to Natural Languages". In U. Reyle and C. Rohrer. Natural Language Parsing and Linguistic Theories. pp. 69–94.
- Gilman, Robert (1996). "A shrinking lemma for indexed languages". Theoretical Computer Science 163 (1–2): 277–281. doi:10.1016/0304-3975(96)00244-7.
|P ≟ NP||This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.|