Indexed language

From Wikipedia, the free encyclopedia

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 automatons. ^[2].

Indexed languages are a proper subset of context-sensitive languages and a proper superset of mildly context-sensitive languages and context-free languages. They qualify as an abstract family of languages and hence satisfy many closure properties. However, they are not closed under intersection or complement. ^[1] Gerald Gazdar has characterized the mildly context-sensitive languages in terms of linear indexed grammars. ^[3]

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.

Contents 1 Examples 2 See also 3 References 4 External links

[edit] Examples

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

^[3]

^[2]

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

^[2]

^[3]

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

[edit] See also

• Chomsky hierarchy
• Indexed grammar
• Mildly context-sensitive language

[edit] References

1. ^ ^{a b} Aho, Alfred (1968). "Indexed grammars—an extension of context-free grammars". Journal of the ACM 15 (4): 647–671. doi:10.1145/321479.321488. http://portal.acm.org/ft_gateway.cfm?id=321488&type=pdf&coll=GUIDE&dl=GUIDE,&CFID=17841194&CFTOKEN=70113868. 
2. ^ ^{a b c} 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. 
3. ^ ^{a b c} 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. 
4. ^ 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. 

[edit] External links

• "NLP in Prolog" chapter on indexed grammars and languages

v • d • e Automata theory: formal languages and formal grammars Chomsky hierarchy Grammars Languages Minimal automaton Type-0 Unrestricted Recursively enumerable Turing machine n/a (no common name) Recursive Decider Type-1 Context-sensitive Context-sensitive Linear-bounded n/a Indexed Indexed Nested stack n/a Tree-adjoining etc. (Mildly context-sensitive) Embedded pushdown Type-2 Context-free Context-free Nondeterministic pushdown n/a Deterministic context-free Deterministic context-free Deterministic pushdown Type-3 Regular Regular Finite n/a n/a Star-free Aperiodic finite Each category of languages or grammars is a proper subset of the category directly above it; and any automaton in each category has an equivalent automaton in the category directly above it.