A basic goal for linguistic theory is to use the most restricted possible formalism. This conflicts with the computational need to have flexible formalisms in case one needs them. Whatever one's stand on this issue, grammar complexity is defined by constraints on types of strings; these constraints are the rules of formal grammars.
A formal grammar is generally described as a structure containing a vocabulary and a set of rules for defining strings on the basis of the vocabulary.
More precisely:
is a set of strings of symbols from a vocabulary 
. The set of all strings over this vocabulary of terminal symbols is denoted by 
(
is the `Kleene star' or `iteration' operator).
, where V is a finite vocabulary of symbols with as a subset, and P is a finite set of rules of the general form 
. The rules define rewriting operations or substitutions which determine the construction and derivation of strings from the vocabulary, in general an infinite number, The symbols in P which are not in belong to the set N of non-terminal symbols.
The general assumptions are made that 
,
and that 
,
Formal grammars and languages are ordered with in a subset or implication relationship along a scale of restrictiveness:
Type 3 
Type 2 Type 1 Type 0