Indexed language

From formulasearchengine
Jump to navigation Jump to search

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 Template:Cnspan 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]

Examples

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

[3]
[2]

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

[2]
[3]

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

Properties

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

References

  1. 1.0 1.1 1.2 1.3 {{#invoke:Citation/CS1|citation |CitationClass=journal }}
  2. 2.0 2.1 2.2 {{#invoke:citation/CS1|citation |CitationClass=book }}
  3. 3.0 3.1 3.2 {{#invoke:citation/CS1|citation |CitationClass=book }}
  4. http://search.proquest.com/docview/303610666
  5. {{#invoke:citation/CS1|citation |CitationClass=book }}
  6. {{#invoke:citation/CS1|citation |CitationClass=book }}
  7. 7.0 7.1 Template:Cite doi
  8. {{#invoke:citation/CS1|citation |CitationClass=book }}
  9. Introduction to automata theory, languages, and computation,[8]Bibliographic notes, p.394-395
  10. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
  11. {{#invoke:citation/CS1|citation |CitationClass=book }}
  12. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
  13. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
  14. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
  15. {{#invoke:Citation/CS1|citation |CitationClass=journal }}

External links

Template:Navbox with columns


Template:Comp-sci-theory-stub