# Generating a Context Free Grammar from a Language

I am wondering how to go from a language such as this:

L = {a^n b^m c^k | n = m or m != k}

To a Context Free Grammar. I know that I would have to turn it into two separate languages but I don't know how to create the production rules for each of those languages.

## 1 Answer

Given $L=\{a^nb^mc^k | \ n=m \ \vee m \neq k \}$ you can see it as $L=L_1 \cup L_2$ where:

• $L_1=\{a^nb^mc^k | \ n=m\}$
• $L_2=\{a^nb^mc^k | \ m \neq k\}$

Then you define 2 Context free grammars $G_1$ and $G_2$ for the 2 languages and in order to express the OR condition your add the production rule

$S \rightarrow S_1\ | \ S_2$

where $S$ is the starting symbol for $G$, $S_1$ for $G_1$ and $S_2$ for $G_2$.

As suggested in the comments, $L_1$ and $L_2$ can be splitted in order to make it easier the design of the grammars.

• $L_1=L_{1,1} \cdot L_{1,2}$ where:

• $L_{1,1}=\{ a^nb^n | \ n \geq 0 \ \}$
• $L_{1,2}=\{ c^k | \ k \geq 0\ \}$
• $L_2=L_{2,1} \cdot (L_{2,2} \vee L_{2,3})$ where:

• $L_{2,1}=\{a^n \ | \ n \geq 0\}$
• $L_{2,2}=\{b^mc^k | \ m < k\}$
• $L_{2,3}=\{b^mc^k | \ m > k\}$
• It may also help to further break down $L_2$ into the cases $m<k$ and $m>k$. – Klaus Draeger Apr 10 '17 at 12:49