Skip to main content
2 of 2
added 62 characters in body
zpavlinovic
  • 1.7k
  • 10
  • 19

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

zpavlinovic
  • 1.7k
  • 10
  • 19