Foundations Of Cognitive Science


In its most general sense, a grammar is a set of rules that can be used to produce expressions (Hopcroft & Ullman, 1979; Parkes, 2002), where an expression is a sequence of symbols.  Any expression will be of finite length, and in a formal grammar an expression can have a length of 0 (i.e. an expression can be empty).  The grammars of interest in the study of logic, language, and computation are called phrase structure grammars; all of the different grammars that fall into the Chomsky hierarchy can be expressed in this form.  A phrase structure grammar has a finite alphabet of nonterminal symbols, including the symbol S from which all expressions are “seeded”, a finite alphabet of terminal symbols, and a finite set of rewrite rules.  A rewrite rule takes the form xy; the rule shows how the expression x can be rewritten as the expression y; these expressions can involve terminal and nonterminal symbols.  The only restriction on this type of rule is that the expression x cannot be empty.  A grammar has produced a grammatical expression in a language when its various rewrite rules have been applied to produce an expression that is comprised only of terminal symbols.

In linguistics, it is assumed that a speaker-hearer’s competence is defined by a particular grammar (Chomsky, 1965), where “grammar” is taken to be a system of the type described above.  A grammar for a linguist describes the abstract knowledge of language that has been internalized in a speaker-hearer, which is separate from such concerns as memory limitations, shifts of attention, and errors which are viewed as being related to performance.  The task of a linguist is to use performance data (e.g. a speaker’s utterances) to infer an underlying grammar.


  1. Chomsky, N. (1965). Aspects Of The Theory Of Syntax. Cambridge, MA: MIT Press.
  2. Hopcroft, J. E., & Ullman, J. D. (1979). Introduction To Automata Theory, Languages, And Computation. Reading, MA: Addison-Wesley.
  3. Parkes, A. (2002). Introduction to Languages, Machines and Logic: Computable Languages, Abstract Machines and Formal Logic. London ; New York: Springer.
(Added September 2010)