Indexed language


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]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Indexed grammar — An indexed grammar is a formal grammar which describes indexed languages. They have three disjoint sets of symbols: the usual terminals and nonterminals and the indices, which appear only in intermediate derivation steps.Productions can replace a …   Wikipedia

  • Language identification in the limit — is a formal model for inductive inference. It was introduced by E. Mark Gold in his paper with the same title [http://www.isrl.uiuc.edu/ amag/langev/paper/gold67limit.html] . In this model, a learner is provided with presentation of some language …   Wikipedia

  • Language Integrated Query — LINQ redirects here. For the card game, see Linq (card game). Language Integrated Query Influenced by SQL, Haskell Language Integrated Query (LINQ, pronounced link ) is a Microsoft .NET Framework component that adds native data querying… …   Wikipedia

  • Mildly context-sensitive language — In formal grammar theory, mildly context sensitive languages are a class of formal languages which can be efficiently parsed, but still possess enough context sensitivity to allow the parsing of natural languages. The concept was first introduced …   Wikipedia

  • Context-sensitive language — In theoretical computer science, a context sensitive language is a formal language that can be defined by a context sensitive grammar. That is one of the four types of grammars in the Chomsky hierarchy. Of the four, this is the least often used,… …   Wikipedia

  • Context-free language — In formal language theory, a context free language is a language generated by some context free grammar. The set of all context free languages is identical to the set of languages accepted by pushdown automata. Contents 1 Examples 2 Closure… …   Wikipedia

  • Recursive language — This article is about a class of formal languages as they are studied in mathematics and theoretical computer science. For computer languages that allow a function to call itself recursively, see Recursion (computer science). In mathematics,… …   Wikipedia

  • Recursively enumerable language — In mathematics, logic and computer science, a recursively enumerable language is a type of formal language which is also called partially decidable or Turing acceptable. It is known as a type 0 language in the Chomsky hierarchy of formal… …   Wikipedia

  • Pipil language (typological overview) — This rather technical article provides a typological sketch of the Pipil language (also known as Nawat). Another related article outlines Pipil grammar in fuller detail. The distinctive purpose of the present article is to single out those… …   Wikipedia

  • Miskito language (typological overview) — This rather technical article provides a typological sketch of the Miskito language. Another related article outlines Miskito grammar in fuller detail. The distinctive purpose of the present article is to single out those specific features of… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.