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

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.

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

• Thank you, that helped me! Dec 16, 2019 at 22:26