Indexed language

Indexed languages are a class of formal languages discovered by Alfred Aho [ cite journal | last = Aho | first = Alfred | year = 1968 | title = Indexed grammars—an extension of context-free grammars | journal = Journal of the ACM | volume = 15 | issue = 4 | pages = 647–671 | issn = 0004-5411 | url = http://portal.acm.org/ft_gateway.cfm?id=321488&type=pdf&coll=GUIDE&dl=GUIDE,&CFID=17841194&CFTOKEN=70113868 | doi = 10.1145/321479.321488 ] ; they are described by indexed grammars and can be recognized by nested stack automatons. cite book | last = Partee | first = Barbara | coauthors = Alice ter Meulen, and Robert E. Wall | title = Mathematical Methods in Linguistics | year = 1990 | publisher = Kluwer Academic Publishers | pages = 536–542 | isbn = 978-90-277-2245-4 ] .

Indexed languages and are a proper subset of context-sensitive languages and a proper superset of mildly context-sensitive languages and context-free languages; they are closed under union, concatenation, and the Kleene closure, but are not closed under intersection or complement. Gerald Gazdar has characterized the mildly context-sensitive languages in terms of linear indexed grammars. cite book | chapter=Applicability of Indexed Grammars to Natural Languages | year=1988 | last=Gazdar | first=Gerald | title=Natural Language Parsing and Linguistic Theories | editor=U. Reyle and C. Rohrer | pages=69-94]

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.

Examples

The following languages are indexed, but are not context-free::$\{a^n\; b^n\; c^n\; d^n|\; n\; geq\; 1\; \}$

:$\{a^n\; b^m\; c^n\; d^m\; |\; m,n\; geq\; 0\; \}$

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

:$\{a^\{2^\{n\; |\; n\; geq\; 0\; \}$

:$\{www\; |\; w\; in\; \{a,b\}^+\; \}$

On the other hand, the following language is not indexed [ cite journal | last = Gilman | first = Robert | year = 1996 | title = A shrinking lemma for indexed languages | journal = Theoretical Computer Science | volume = 163 | issue = 1-2 | pages = 277–281 | doi = 10.1016/0304-3975(96)00244-7 ] ::$\{(a\; b^n)^n\; |\; n\; geq\; 0\; \}$

ee also

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

References

External links

* [http://www.cogs.susx.ac.uk/research/nlp/gazdar/nlp-in-prolog/ch04/chapter-04-sh-1.6.3.html#sh-1.6.3 "NLP in Prolog" chapter on indexed grammars and languages]