0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Possible duplicate of How to prove that a language is context-free? $\endgroup$
    – David Richerby
    Apr 10, 2017 at 12:52
  • $\begingroup$ It looks like you might have accidentally created two accounts. I encourage you to merge them, to ensure you retain ability to edit and comment on your own question. $\endgroup$
    – D.W. ♦
    Apr 10, 2017 at 16:41

1 Answer 1

Reset to default
1
$\begingroup$

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\}$
Improve this answer
$\endgroup$
1
  • 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, 2017 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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