Context-Free Languages
In this chapter we study context-free grammars and languages. We define
de11vation trees and give methods of simplifying context-free grammars. The
two normal forms-Chomsky normal form and Greibach normal form-are
dealt \\,ith. We conclude this chapter after proving pumping lemma and giving
some decision algorithms.
6.1 CONTEXT-FREE LANGUAGES AND DERIVATION
TREES
Context-free languages are applied in parser design. They are also useful for
describing block structures in programming languages. It is easy to visualize
derivations in context-free languages as we can represent derivations using tree
structures.
Let us reca11 the definition of a context-free, grammar (CFG). G is
context-free if every production is of the form A ~ a, where A E V N and
a E CVv U L)*.
EXAMPLE 6.1
Construct a context-free grammar G generating all integers (with sign).
Solution
Let
G = (Vv. L, P, S)
where
V v = {S, (sign), (digit). (Integer)}
L = {a, L 2. 3, ..., 9, +, -}
180