Let A and D be contextfree languages over the same alphabet

Let A and D be context-free languages over the same alphabet sigma. Prove that the union A B of A and B is also context-free. Prove that the concatenation AB of A and B is also context-free. Prove that the star A* of A is also context-free.

Solution

a.) Let L= L1 U L2. then we introduce S as the start symbol for L like this: S -> S1|S2 where S1 and S2 are start symbol for L1 and L2, all other rules for L1 and L2 remains. So we have built a grammer for L and hence L is context free.

b.) The grammer of L = L1L2 has new start symbol S and the rule S-> S1S2 is added along with other rules, which shows that L is also Context free.

c) L = L1* has again new start symbol S and rule S-> SS1| epsilon, in addition to other rules of L1. This L is also context free.