Question

Show that the class of context-free languages is closed under concatenation.

Answer 1

Let L1 and L2 are context free languages. Context free grammar for L1 and L2 are G1 and G2 respectively.

If starting symbols of G1 and G2 are S1 and S2, then for two grammars to be concatenated, we can create a new start symbol with production as S-> S₁S₂. The result grammar will a new CFG which generates the concatenation of L1 and L2. Therefore, concatenation is closed in Context-free languages.

For example, L1 = {aⁿbⁿ | n >=0} and L2 = {ww^r | w belongs to (a,b)}

The G1 will be:

S₁ -> aS₁b | Λ

And G2 is :

S₂ -> aS₂a | bS₂b | Λ

And resultant grammar for L1.L2 will be:

S -> S₁S₂

S₁ -> aS₁b | Λ

S₂ -> aS₂a | bS₂b | Λ