1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ $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 $\endgroup$
    – Sebastian
    Nov 19 '13 at 9:06
6
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.