World Library  
Flag as Inappropriate
Email this Article

Indexed language

Article Id: WHEBN0007324284
Reproduction Date:

Title: Indexed language  
Author: World Heritage Encyclopedia
Language: English
Subject: Context-sensitive language, Formal language, Combinatory categorial grammar, Aperiodic finite state automaton, Embedded pushdown automaton
Publisher: World Heritage Encyclopedia

Indexed language

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

Indexed languages are a proper subset of context-sensitive languages.[1] 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.[1]

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.

Gerald Gazdar (1988)[3] and Vijay-Shanker (1987)[4] introduced a mildly context-sensitive language class now known as linear indexed grammars (LIG).[5] Linear indexed grammars have additional restrictions relative to IG. LIGs are weakly equivalent (generate the same language class) as tree adjoining grammars.[6]


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

\{a^n b^n c^n d^n| n \geq 1 \} [3]
\{a^n b^m c^n d^m | m,n \geq 0 \} [2]

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

\{a^{2^{n}} | n \geq 0 \} [2]
\{www | w \in \{a,b\}^+ \} [3]

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

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


Hopcroft and Ullman tend to consider indexed languages as a "natural" class, since they are generated by several formalisms, such as:[9]

Hayashi[14] generalized the pumping lemma to indexed grammars. Conversely, Gilman[7][15] gives a "shrinking lemma" for indexed languages.

See also


  1. ^ a b c d  
  2. ^ a b c  
  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. ^
  5. ^ Laura Kallmeyer (2010). Parsing Beyond Context-Free Grammars. Springer Science & Business Media. p. 31.  
  6. ^ Laura Kallmeyer (16 August 2010). Parsing Beyond Context-Free Grammars. Springer Science & Business Media. p. 32.  
  7. ^ a b Gilman, Robert H. (1996). "A Shrinking Lemma for Indexed Languages". Theoretical Computer Science 163 (1–2): 277–281.  
  8. ^  
  9. ^ Introduction to automata theory, languages, and computation,[8]Bibliographic notes, p.394-395
  10. ^ Alfred Aho (1969). "Nested Stack Automata". Journal of the ACM 16 (3): 383–406.  
  11. ^ Michael J. Fischer (1968). "Grammars with Macro-Like Productions". Proc. 9th Ann. IEEE Symp. on Switching and Automata Theory (SWAT). pp. 131–142. 
  12. ^ Sheila A. Greibach (1970). "Full AFL's and Nested Iterated Substitution". Information and Control 16 (1): 7–35.  
  13. ^ T.S.E. Maibaum (1974). "A Generalized Approach to Formal Languages". J. Computer and System Sciences 8 (3): 409–439.  
  14. ^ T. Hayashi (1973). Theorem"uvxyz"On Derivation Trees of Indexed Grammars - An Extension of the . Publication of the Research Institute for Mathematical Sciences (Research Institute for Mathematical Sciences) 9 (1): 61–92.  
  15. ^ Robert H. Gilman (Sep 1995). "A Shrinking Lemma for Indexed Languages". 

External links

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

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from World eBook Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.