contextfree language
A contextfree language is a language^{} over some alphabet that can be generated from a particular kind of a known as a contextfree grammar.
Formally, a contextfree grammar is a formal grammar $G=(\mathrm{\Sigma},N,P,\sigma )$ whose productions in $P$ have the form
$$X\to w,$$ 
where $X\in N$ and $w\in {\mathrm{\Sigma}}^{*}$. A contextfree language is the formal language $L(G)$ generated by a contextfree grammar $G$. In other words,
$$L(G):=\{v\in {T}^{*}\mid \sigma \stackrel{*}{\to}v\},$$ 
where $T:=\mathrm{\Sigma}N$ is the set of terminals, and $\sigma \stackrel{*}{\to}v$ simply means that the productions in $P$ are applied a finite number of times to the starting symbol $\sigma $ so that $v$ is reached in the end.
This formal definition is not initially very enlightening. As an example, consider typical infix arithmetic notation. An expression typically consists of one or more terms, joined together by operators with varying precedence.
Parentheses can be used to override operator precedence. This syntax is a contextfree language. Let us describe such expressions with the operators +
and 
with lowest precedence, and *
and /
with highest precedence, where all operators are leftassociative and the only other allowed symbols are integer literals^{} and parentheses.
$T$  $:=$  $\{\mathrm{\U0001d7f6},\mathrm{\U0001d7f7},\mathrm{\U0001d7f8},\mathrm{\U0001d7f9},\mathrm{\U0001d7fa},\mathrm{\U0001d7fb},\mathrm{\U0001d7fc},\mathrm{\U0001d7fd},\mathrm{\U0001d7fe},\mathrm{\U0001d7ff},(,),+,,*,/\}$  
$N$  $:=$  $\{S,A,B,C,D\}$  
$P$  $:=$  $\mathrm{\{}(S,A),(S,S+A),(S,SA),$  
$(A,B),(A,A*B),(A,A/B),$  
$(B,C),(B,(S)),(C,D),(C,CD),$  
$(D,\mathrm{\U0001d7f6}),(D,\mathrm{\U0001d7f7}),(D,\mathrm{\U0001d7f8}),(D,\mathrm{\U0001d7f9}),(D,\mathrm{\U0001d7fa}),(D,\mathrm{\U0001d7fb}),(D,\mathrm{\U0001d7fc}),(D,\mathrm{\U0001d7fd}),(D,\mathrm{\U0001d7fe}),(D,\mathrm{\U0001d7ff})\}$  
$\sigma $  $:=$  $S$ 
It can be shown that the languages of the classical propositional logic^{} and predicate logic are both contextfree.
Contextfree grammars are also known as Type2 grammars in the Chomsky hierarchy. The Chomsky hierarchy specifies Type2 grammars as consisting only of production rules of the form $A\to \gamma $, where $A$ is a nonterminal and $\gamma $ is a string of terminals and nonterminals.
Remarks.

1.
A contextfree grammar can be represented by a pushdown automaton. The automaton serves both as an acceptor for the language (that is, it can decide whether or not any arbitrary sentence^{} is in the language) and as a generator^{} for the language (that is, it can generate any finite sentence in the language in finite time).

2.
The syntaxes of most programming languages are contextfree grammars (or very close to it). A very useful subset of contextfree languages are regular languages.

3.
A contextfree grammar $G$ is contextsensitive if none of its productions has the form $X\to \lambda $, where $\lambda $ is the empty word^{}.

4.
The family of contextfree languages has the following closure properties: union, concatenation^{}, Kleene star, homomorphism^{}, inverse^{} homomorphism, reversal, and intersection^{} with a regular language. However, it is not closed under intersection, set difference^{}, and complementation.
References
 1 S. Ginsburg The Mathematical Theory of ContextFree Languages. McGrawHill, New York (1966).
Title  contextfree language 
Canonical name  ContextfreeLanguage 
Date of creation  20130322 12:26:28 
Last modified on  20130322 12:26:28 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  33 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 68Q45 
Classification  msc 68Q42 
Synonym  type2 language 
Synonym  type2 grammar 
Related topic  Language 
Related topic  RegularLanguage 
Related topic  DeterministicFiniteAutomaton 
Related topic  NonDeterministicFiniteAutomaton 
Related topic  PushdownAutomaton 
Related topic  ContextSensitiveLanguage 
Related topic  DeterministicPushdownAutomaton 
Defines  contextfree 
Defines  contextfree grammar 