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

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.

• $0^n 1^n$ is not a Kleene star operation since the number of 0s and 1s is coupled. Your grammar for this language is correct ($A$ could be eliminated though). The answer of bellpeace shows how to do the actual Kleene star and union Nov 19 '13 at 9:06

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$.