Show that the class of context-free languages is closed under the regular operations, union, concatenation, and star.

The context free language is generated by context free grammar. These languages are accepted by Pushdown Automata. These are the superset of regular languages.

Consider context-free languages $L_1$described as $G_1=(V_1,S,R_1,S_1).$

Consider context-free language $L_2$ described as $G_2=(V_2,S,R_2,S_2).$

Consider the following grammar

$G_{union}$$=(V_1\cup V_2,\cup \left\{S\right\},S,R_1\cup R_2\cup \left\{\left(S\to S1\right),\left(S\to S2\right)\right\},S)$

The grammar describes $G_{union}$describes $L_1\cup L_2$.

Add S to the variables. Also, add the rule

$S\to S1|S2$.

Thus, context-free languages are closed under the union operator.

Consider the grammar

$G_{concatenation}$$=(V_1\cup V_2,\cup \left\{S\right\},S,R_1\cup R_2\cup \left\{\left(S\to S1S2\right)\right\},S)$

The grammar $G_{concatenation}$describes,

$L1oL2.S\to S1S2$is added to the rules

Thus, context-free languages are closed under the concatenation operator.

Consider the grammar

$G_{star}$$=(V1\cup \left\{S\right\},S,R1\cup \left\{\left(S\to \epsilon \right),\left(S\to S1S1\right)\right\},S)$

The grammar $G_{star}$describes $L1*$.

The rule$S\to \epsilon |S1S1$ is added to the rules.

Thus, context-free languages are closed under the star operator.