I want to find a Context-Free Grammar for $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$

I've tried the following:

$G=(V,\Sigma,R,S)$ with $\Sigma=\{a,b,c,\lambda\}$, $V=\{S,B\}$, $S=S$ and $$R=\{S\to \lambda\mid aSc\mid B,\;B\to bBc\mid \lambda\},$$ which would output $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$, in my opinion. I've tried to test my grammar by applying the rules in different combinations and I didn't spot any error yet.

So I'm asking myself:
Is there a way to to see if $L(G)=L$ or do I need to assume, that I've done everything correctly after testing some cases?


1 Answer 1

  1. $S\to\lambda$ is unnecessary because $S\to B$ and $B\to\lambda$.
  2. The grammar recognizes the desired language.

You can prove the second assertion pretty easily using induction (for example on the length of the derivation, or the length of the sentence).

You'll probably find it easier to prove two assertions independently:

  1. If a sentence is in $L$, then it is in $L(G)$.
  2. If a sentence is in $L(G)$, then it is in $L$.

Together, these prove equivalence.

  • $\begingroup$ Thank you, that helped me! $\endgroup$
    – Doesbaddel
    Commented Dec 16, 2019 at 22:26

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.