Formal language theory

From Wikipedia, the free encyclopedia

Formal language theory is a field of computer science which studies formal languages.^[1] These languages are often arranged via the Chomsky hierarchy, which classifies languages based on the types of formal grammars that define them. The study of formal languages and grammars is also of key interest in theoretical linguistics (Grishman 1986).

[edit] Notes

1. ^ Hopcroft, Motwani, and Ullman (2000) is a standard textbook in the area.

[edit] References

• Ralph Grishman. 1986. Computational Linguistics: An Introduction, Cambridge University Press. ISBN 0521310385
• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. 2000. Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2nd edition. ISBN 0201441241
• Peter Linz. 2006. An Introduction to Formal Language and Automata, Jones & Bartlett, 4th edition.ISBN 0763737984

v • d • e 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 computer science article is a stub. You can help Wikipedia by expanding it.