Login
Login

Indexed language

Indexed languages are a class of formal languages discovered by Alfred Aho;{{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 }} they are described by indexed grammars and can be recognized by nested stack automata.{{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 }}

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.

The class of indexed languages has {{cnspan|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){{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 }} and Vijay-Shanker (1987){{cite thesis |last1=Vijayashanker |first1=K. |year=1987 |title=A study of tree adjoining grammars |id={{ProQuest|303610666}} }} introduced a mildly context-sensitive language class now known as linear indexed grammars (LIG).{{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 }} Linear indexed grammars have additional restrictions relative to IG. LIGs are weakly equivalent (generate the same language class) as tree adjoining grammars.{{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 }}

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 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}}

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

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,{{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 }} Bibliographic notes, p.394-395}}

  • Aho's indexed grammars
  • Aho's one-way nested stack automata{{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 }}
  • Fischer's macro grammars{{cite conference |last1=Fischer |first1=Michael J. |title=9th Annual Symposium on Switching and Automata Theory (Swat 1968) |chapter=Grammars with macro-like productions |conference=9th Annual Symposium on Switching and Automata Theory (swat 1968) |date=October 1968 |pages=131–142 |doi=10.1109/SWAT.1968.12 }}
  • Greibach's automata with stacks of stacks{{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= }}
  • Maibaum's algebraic characterization{{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 }}

Hayashi{{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 }} generalized the pumping lemma to indexed grammars.

Conversely, Gilman gives a "shrinking lemma" for indexed languages.

See also

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