How does the kleene star and union work in a context free grammar?

Question

Im in a functional languages computer science class and I have a question on the use of the kleene star and the Union in a context free grammar.

for the kleene star I have an idea of how I might do it. for example

 {0^n 1^n | n in the set of natural numbers} 

I think it would look something like this.

 S-> 0S1 | A
 A-> S | lambda

where lambda would mark closing or ending the string. Is this right?

as for how the union would I dont understand at all how it would work. wer were given an example that looks like this

 {0^n1^n | n in the set of natural nubmer} U 
 {0^n1^2n | n in the set of natural numbers}

I know how I would make a context free grammar for either of these alone but I dont know how the union comes into play with this.

Answer 1

This is how you can implement star and union operations over context-free languages given their grammars.

Given a grammar $G$ for the language $L$, we can take a new non-terminal symbol $T$ not appearing in $G$, and add the following production:

$$ T \rightarrow TS \;|\; \epsilon$$

where $S$ is the start symbol of $G$. $T$ is now a new start symbol. The language of the resulting grammar is $L^{*}$.

Similarly, given grammars $G_1$ and $G_2$ for languages $L_1$ and $L_2$, respectively, we can take a new non-terminal symbol $T$ not appearing in $G_1$ nor in $G_2$, and add the following production:

$$T \rightarrow S_1 \;| \;S_2 $$

where $S_1$ and $S_2$ are the starting symbols of $G_1$ and $G_2$, respectively. $T$ is now a new start symbol. The language of the resulting grammar is $L_1 \cup L_2$. Also, make sure that you use different non-terminal symbols in $G_1$ ad $G_2$.