context-free languages has important applications in the design of programming
languages as well as in the construction of efficient compilers. We touch upon
this briefly in Section 5.3.
5.1 Context-Free Grammars
The productions in a regular grammar are restricted in two ways: The left side
must be a single variable, while the right side has a special form. To create
grammars that are more powerful, we must relax some of these restrictions. By
retaining the restriction on the left side, but permitting anything on the right, we
get context-free grammars.
Definition 5.1
A grammar G = (V, T, S, P) is said to be context-free if all productions in P have
the form
where A ∈ V and x ∈ (V ∪ T) * .
A language L is said to be context-free if and only if there is a context-free
grammar G such that L = L (G).
Every regular grammar is context-free, so a regular language is also a
context-free one. But, as we know from simple examples such as {a n b n }, there
are nonregular languages. We have already shown in Example 1.11 that this
language can be generated by a context-free grammar, so we see that the family
of regular languages is a proper subset of the family of context-free languages.
Context-free grammars derive their name from the fact that the substitution
of the variable on the left of a production can be made any time such a variable
appears in a sentential form. It does not depend on the symbols in the rest of the
sentential form (the context). This feature is the consequence of allowing only a
single variable on the left side of the production.
Examples of Context-Free Languages