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.


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\}$
  • 1
    $\begingroup$ It may also help to further break down $L_2$ into the cases $m<k$ and $m>k$. $\endgroup$ – Klaus Draeger Apr 10 '17 at 12:49

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.