


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 x → y; 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 speakerhearer’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 speakerhearer, 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.
References:
 Chomsky, N. (1965). Aspects Of The Theory Of Syntax. Cambridge, MA: MIT Press.
 Hopcroft, J. E., & Ullman, J. D. (1979). Introduction To Automata Theory, Languages, And Computation. Reading, MA: AddisonWesley.
 Parkes, A. (2002). Introduction to Languages, Machines and Logic: Computable Languages, Abstract Machines and Formal Logic. London ; New York: Springer.
(Added September 2010)



