91Ó°ÊÓ

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∪V_2,∪\left\{S\right\},S,R_1∪R_2∪\left\{\left(S→S1\right),\left(S→S2\right)\right\},S)$

The grammar describes $G_{union}$describes $L_1∪L_2$.

Add S to the variables. Also, add the rule

$S→S1|S2$.

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

Consider the grammar

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

The grammar $G_{concatenation}$describes,

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

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

Consider the grammar

$G_{star}$$=(V1∪\left\{S\right\},S,R1∪\left\{\left(S→\mathrm{Î\mu }\right),\left(S→S1S1\right)\right\},S)$

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

The rule$S→\mathrm{Î\mu }|S1S1$ is added to the rules.

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