1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$
  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.

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

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.