{{Short description|Formal languages in computing}} {{multiple issues| {{too detailed|date=May 2026}} {{more categories|date=May 2026}} }} '''Indexed languages''' are a class of formal languages discovered by Alfred Aho;<ref name="aho1968">{{cite journal | last = Aho | author-link = Alfred Aho | first = Alfred | s2cid = 9539666 | year = 1968 | title = Indexed grammars—an extension of context-free grammars | journal = Journal of the ACM | volume = 15 | issue = 4 | pages = 647–671 | doi = 10.1145/321479.321488 | doi-access = free }}</ref> they are described by indexed grammars and can be recognized by nested stack automata.<ref name="partee_etal_1990">{{cite book |author-link=Barbara Partee |last1=Partee |first1=Barbara |first2= Alice |last2=ter Meulen|author2-link=Alice ter Meulen |first3=Robert E. |last3=Wall |title=Mathematical Methods in Linguistics |year=1990 |publisher=Kluwer Academic Publishers |pages=536–542 |isbn=978-90-277-2245-4 }}</ref>
Indexed languages are a proper subset of context-sensitive languages.<ref name="aho1968"/> 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.<ref name="aho1968" />
The class of indexed languages has {{citation needed span|practical importance in natural language processing as a computationally affordable|date=August 2014}} generalization of context-free languages, since indexed grammars can describe many of the nonlocal constraints occurring in natural languages.
Gerald Gazdar (1988)<ref name="gazdar1998">{{cite book |last1=Gazdar |first1=Gerald |chapter=Applicability of Indexed Grammars to Natural Languages |pages=69–94 |doi=10.1007/978-94-009-1337-0_3 |editor1-first=U. |editor1-last=Reyle |editor2-first=C. |editor2-last=Rohrer |title=Natural Language Parsing and Linguistic Theories |series=Studies in Linguistics and Philosophy |date=1988 |volume=35 |publisher=Springer Netherlands |isbn=978-94-009-1337-0 }}</ref> and Vijayashanker (1987)<ref>{{cite thesis |last1=Vijayashanker |first1=K. |year=1987 |title=A study of tree adjoining grammars |id={{ProQuest|303610666}} }}</ref> introduced a mildly context-sensitive language class now known as linear indexed grammars (LIG).<ref name="Kallmeyer2010">{{cite book |first1=Laura |last1=Kallmeyer |title=Parsing Beyond Context-Free Grammars |url=https://books.google.com/books?id=F5wC0dko1L4C&pg=PA31 |year=2010 |publisher=Springer |isbn=978-3-642-14846-0 |page=31 }}</ref> Linear indexed grammars have additional restrictions relative to indexed grammars. LIGs are weakly equivalent (generate the same language class) as tree adjoining grammars.<ref name="Kallmeyer2010b">{{cite book |first1=Laura |last1=Kallmeyer |title=Parsing Beyond Context-Free Grammars |url=https://books.google.com/books?id=F5wC0dko1L4C&pg=PA32 |date=16 August 2010 |publisher=Springer |isbn=978-3-642-14846-0 |page=32 }}</ref>
==Examples==
The following languages are indexed, but are not context-free: :<math> \{a^n b^n c^n d^n| n \geq 1 \} </math> <ref name="gazdar1998"/>
:<math> \{a^n b^m c^n d^m | m,n \geq 0 \}</math> <ref name="partee_etal_1990"/>
These two languages are also indexed, but are not even mildly context sensitive under Gazdar's characterization:
:<math> \{a^{2^{n}} | n \geq 0 \}</math> <ref name="partee_etal_1990"/>
:<math> \{www | w \in \{a,b\}^+ \}</math> <ref name="gazdar1998"/>
On the other hand, the following language is not indexed:<ref name="Gilman.1996">{{cite journal| last = Gilman | first = Robert H. | s2cid = 14479068 | title=A Shrinking Lemma for Indexed Languages| journal=Theoretical Computer Science| year=1996| volume=163| issue = 1–2 | pages=277–281| doi = 10.1016/0304-3975(96)00244-7| arxiv=math/9509205}}</ref> :<math>\{(a b^n)^n | n \geq 0 \}</math>
==Properties==
Hopcroft and Ullman tend to consider indexed languages as a "natural" class, since they are generated by several formalisms, such as:{{#tag:ref|Introduction to automata theory, languages, and computation,<ref name="hopcroft_ullman_1979">{{cite book |author-link= John Hopcroft |last1=Hopcroft |first1=John |first2=Jeffrey |last2=Ullman |author2link=Jeffrey Ullman |title=Introduction to automata theory, languages, and computation |year=1979 |publisher=Addison-Wesley |isbn=978-0-201-02988-8 |url=https://archive.org/details/introductiontoau00hopc/page/390 |page=390 }}</ref> Bibliographic notes, p.394-395}} * Aho's indexed grammars<ref name="aho1968"/> * Aho's one-way nested stack automata<ref>{{cite journal |last1=Aho |first1=Alfred V. |s2cid=685569 |title=Nested Stack Automata |journal=Journal of the ACM |date=July 1969 |volume=16 |issue=3 |pages=383–406 |doi=10.1145/321526.321529 |doi-access=free }}</ref> * Fischer's macro grammars<ref>{{cite conference |last1=Fischer |first1=Michael J. |title=9th Annual Symposium on Switching and Automata Theory (Swat 1968) |chapter=Grammars with macro-like productions |date=October 1968 |pages=131–142 |doi=10.1109/SWAT.1968.12 }}</ref> * Greibach's automata with stacks of stacks<ref>{{cite journal |last1=Greibach |first1=Sheila A. |title=Full AFLs and nested iterated substitution |journal=Information and Control |date=March 1970 |volume=16 |issue=1 |pages=7–35 |doi=10.1016/s0019-9958(70)80039-0 |doi-access= }}</ref> * Maibaum's algebraic characterization<ref>{{cite journal |last1=Maibaum |first1=T.S.E. |title=A generalized approach to formal languages |journal=Journal of Computer and System Sciences |date=June 1974 |volume=8 |issue=3 |pages=409–439 |doi=10.1016/s0022-0000(74)80031-0 |doi-access=free }}</ref>
Hayashi<ref>{{cite journal |last1=Hayashi |first1=Takeshi |title=On derivation trees of indexed grammars: an extension of the {$uvwxy$}-theorem |journal=Publications of the Research Institute for Mathematical Sciences |date=1973 |volume=9 |issue=1 |pages=61–92 |doi=10.2977/prims/1195192738 |doi-access=free }}</ref> generalized the pumping lemma to indexed grammars. Conversely, Gilman<ref name="Gilman.1996"/> gives a "shrinking lemma" for indexed languages.
==See also== * Chomsky hierarchy
==References==
{{Reflist}}
==External links== * [https://web.archive.org/web/20070311042935/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]
{{Formal languages and grammars}}
{{DEFAULTSORT:Indexed Language}} Category:Formal languages Category:Computational linguistics