Problem Solving in Automata, Languages, and Complexity

104 CONTEXT-FREE LANGUAGES

Theorem 3.17 The class of context-free languages are closed under union,
concatenation, and Kleene closure.

Proof. Let Lr and L2 be two context-free languages, generated by grammars

G1 and Gz, respectively. Assume that Gi = (Vi, Ci, &,Si) for i = 1,2, and

that VInV2 = 0. (If vImi # 0, we can simply rename all nonterminal symbols

in V2 to be different from those in VI .) Also assume that Ss, S4 6 VI U V&

Then, it is easy to check the following:

(1) Language L1 U L2 is generated by grammar Ga = (VI U V2 U {Sa}, IZl U

x2, R3, S3), where

R3= R1uR2u{S3+S1 IS,}.

(2) Language L1 L2 is generated by Gd = (VI U V2 U {&}, Cl U &, RJ, &),

where

R4 = RI u R2 u {& + S1S2}.

(3) Language L; is generated by Gs = (VI, Cl, Rg, Sl), where

R5 = RI u {S1 + SISl 1 E}. cl

Recall the operation of substitution on languages, defined in Section 2.6.

Theorem 3.18 Assume that L C C* is a context-free language, and that f is
a substitution with the property that f( a ) is a context-free language for every
a E C. Then, f(L) is context-free.

Proof. Suppose that L is generated by the context-free grammar G = (V, C, R,

S) and, for every a E C, the language f( ) l is g a enerated by the context-free

grammar G, = (V&C,, RJ,). Assume that Va n V = Va n Vb = 8 for all

a#bEC.

Then, f(L) is generated by Gf = (Vf , Cf , Rf , S), where

Vf = V u ( u Va) , EJ = u c,, Rj = R’ u ( u R”> ,

aEC aEC aEC

and R’ is the set of rules in R with each symbol a E C replaced by Sa. •I

We now apply these closure properties to construct context-free grammars.

Example 3.19 Find a context-free grammar generating

L = {Omln 1 m # n,m,n > - 0).

Solution. Note that L = L1 U L2, where L1 = {Onln 1 m > n > 0}, and
L2 = {Omln 1 n > m > 0). It is clear that L1 can be generated by the
following rules: -
s1 __) 0 1 OS1 1 OS~l,