Indexed language: Information from Answers.com

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

Indexed languages are a proper subset of context-sensitive languages and a proper superset of mildly context-sensitive languages and context-free languages. They qualify as an abstract family of languages and hence satisfy many closure properties. However, they are not closed under intersection or complement. ^[1] Gerald Gazdar has characterized the mildly context-sensitive languages in terms of linear indexed grammars. ^[3]

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.

1 Examples
2 See also
3 References
4 External links

Examples

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 ^[4]:

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

References

^ ^a ^b Aho, Alfred (1968). "Indexed grammars—an extension of context-free grammars". Journal of the ACM 15 (4): 647–671. doi:10.1145/321479.321488. http://portal.acm.org/ft_gateway.cfm?id=321488&type=pdf&coll=GUIDE&dl=GUIDE,&CFID=17841194&CFTOKEN=70113868.
^ ^a ^b ^c Partee, Barbara; Alice ter Meulen, and Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers. pp. 536–542. ISBN 978-90-277-2245-4.
^ ^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.
^ Gilman, Robert (1996). "A shrinking lemma for indexed languages". Theoretical Computer Science 163 (1-2): 277–281. doi:10.1016/0304-3975(96)00244-7.

External links

"NLP in Prolog" chapter on indexed grammars and languages

This mathematical logic-related article is a stub. You can help Wikipedia by expanding it.

Automata theory: formal languages and formal grammars

Chomsky hierarchy	Grammars	Languages	Minimal automaton
Type-0	Unrestricted	Recursively enumerable	Turing machine
n/a	(no common name)	Recursive	Decider
Type-1	Context-sensitive	Context-sensitive	Linear-bounded
n/a	Indexed	Indexed	Nested stack
n/a	Tree-adjoining etc.	(Mildly context-sensitive)	Embedded pushdown
Type-2	Context-free	Context-free	Nondeterministic pushdown
n/a	Deterministic context-free	Deterministic context-free	Deterministic pushdown
Type-3	Regular	Regular	Finite
n/a	n/a	Star-free	Aperiodic finite

Each category of languages or grammars is a proper subset of the category directly above it;
and any automaton in each category has an equivalent automaton in the category directly above it.

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

	In American Sign Language what is the meaning of waving your index finger up and down? Read answer...
	Why is index cards called index? Read answer...
	What is a index in algebra? Read answer...

	What is the default index of an array's first position in most languages?
	Why does array index start with zero in C language?
	How do you interpret item discrmination index of a language test item?

Indexed language

Contents

Examples

See also

References

External links