Grammar
A grammar defining formal language 
is a quadruple
, where 
is a finite set
of nonterminals, 
is a finite set of terminal symbols,
is a finite set of productions, and 
is an element of
.
The set 
of terminal symbols is 
's alphabet. Nonterminals
are symbols representing language constructs. The sets 
and 
should not intersect.
is called the start symbol. Productions are rules
of the form: 
, where both 
and 
are strings
of terminals and nonterminals, 
contains at
least one nonterminal.
Sentential forms for grammar 
are defined by the following
rules: 
is a sentential form and if 
is
a sentential form and production 
belongs
to 
, then 
is a sentential form as well.
is the set of all strings which are sentential
forms consisting entirely of terminal symbols. For a language defined by a grammar,
recognition whether a given string (expression) belongs to that language is, in general,
a non-trivial task. All languages defined by grammars are recursively
enumerable sets.
1. A grammar 
is called right linear if all its productions
have the form 
or 
, where
and 
is a string
of terminal symbols.
2. A grammar 
is called context-free if all its productions
have the form 
, where 
and 
is a string of terminal and nonterminal symbols.
3. A grammar 
is called context-sensitive if all its
productions have the form 
, where both 
and 
are strings
of terminal and nonterminal symbols and the length of 
is not more
than the length of 
.
4. A grammar 
is called unrestricted if it does not
belong to categories 1 through 3.
This hierarchy of grammars was introduced by N. Chomsky. The set of languages defined by grammars of every category is a proper superset of that for the previous category. The languages defined by grammars of categories 1 through 3 are recursive sets. A language can be defined by a grammar of category 1 iff it is defined by a regular expression.
Contact the MathWorld Team
{12, 20} . {16, -5}