Context-free language – a formal language, which is defined by the set
of context-free rules. A production is context-free if and only if:
A ::= ξ (A ∈ N, ξ ∈(N ∪ T)*)
The left side of a context-free production consists of a single non-terminal symbol and can be replaced regardless of the context A appears in. If the production has the form of:
αAβ:: = αξβ
it is called a context-sensitive production, because a replacement by
A can happen only in the context of α and β.
Example 1:
This example incorporates a grammar in which, by means of recursion, an
infinite number of sentences can be generated by means of a finite
set of productions.
S ::= xA
A ::= z|yA
Set of sentences that can be generated from start symbol S:
xz
xyz xyyz xyyyz ...