Indexed language

From Wikipedia, the free encyclopedia

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 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. [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.

Contents

[edit] 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 \}

[edit] See also

[edit] References

  1. ^ Aho, Alfred (1968). "Indexed grammars—an extension of context-free grammars". Journal of the ACM 15 (4): 647–671. doi:10.1145/321479.321488. ISSN 0004-5411. 
  2. ^ a b c Partee, Barbara; Alice ter Meulen, and Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers, 536–542. ISBN 978-90-277-2245-4. 
  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, 69-94. 
  4. ^ 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. 

[edit] External links


 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 Star-free Counter-Free
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.
Languages