Chomsky Hierarchy

In computer science, a formal description of any class of languages (human or otherwise) relates its complexity to the complexity of a computing device that could generate or accept it (Hopcroft & Ullman, 1979; Révész, 1983).  This has resulted in a classification of grammars known as the Chomsky hierarchy (Chomsky, 1959).  In the Chomsky hierarchy, the simplest grammars are regular, and can be accommodated by finite state automata.  The next most complicated are context-free grammars, which can be processed by pushdown automata (a device that is a finite state automaton with a finite internal memory).  Next are the context-sensitive grammars, which are the domain of linear bounded automata (i.e., a device like a Turing machine, but with a ticker tape of bounded length).  The most complex grammars are the phrase structure grammars, which can only be dealt with by Turing machines.

The Chomsky hierarchy is important in cognitive science because the complexity of a grammar in the hierarchy can be used to evaluate (at the computational level) theoretical proposals within cognitive science.  For instance, the famous terminal metapostulate critique (Bever, Fodor, & Garrett, 1968) is basically an argument that the grammatical capabilities of associative theories are too weak to account for the more sophisticated abilities of humans.  In other words, grammars accommodated by associative devices (i.e. finite state automata) fall in the wrong place in the Chomsky hierarchy to be of interest to cognitive science.

References:

1. Bever, T. G., Fodor, J. A., & Garrett, M. (1968). A formal limitation of associationism. In T. R. Dixon & D. L. Horton (Eds.), Verbal Behavior And General Behavior Theory (pp. 582-585). Englewood Cliffs, NJ: Prentice-Hall.
2. Chomsky, N. (1959). On certain formal properties of grammars. Information and Control, 2, 137-167.
3. Hopcroft, J. E., & Ullman, J. D. (1979). Introduction To Automata Theory, Languages, And Computation. Reading, MA: Addison-Wesley.
4. Révész, G. E. (1983). Introduction to Formal Languages. New York: McGraw-Hill.

(Added September 2010)