# Construct context free grammar from language

I have been starting to learn about CFGs and PDAs and have gotten familiar with the simple stuff. I have been able to construct CFGs for simple languages but this question is more specific:

$\lbrace 0^a1^b2^c3^d4^e5^f |a,b,c,d,e,f \geq 0$ and $a+b=d+e\rbrace$.

My thought process has only gone so far. I see that if you add a 0 you must add a 3 or 4, the same is if you add a 1. And for adding a 3 or 4 the case is very similar. My biggest troubles are due to the characters that lay between the pairs of 0s,1s,3s and 4s. I haven't been able to produce a serious attempt yet, but will post it as an edit if I do. Any help would be appreciated.

Edit: Here is a possible solution I have come to:

$S\rightarrow AB$

$A\rightarrow 0A4|C|D$

$B\rightarrow B5|\epsilon$

$C\rightarrow 0C3|E$

$D\rightarrow 1D4|E$

$E\rightarrow 1E3|F$

$F\rightarrow 2F|\epsilon$.

You are right, the point is having nonterminals that sheds 0 and 4, or 0 and 3, or 1 and 4, or 1 and 3, switching from one to the other to get the $0^1 1^b$ and corresponding $3^d 4^e$; once you have that, go to one that repeats to make $2^c$ in between. The $5^f$ is easy to append.
• Ok I believe I understand this. Do you think I can start with $\lbrace 0^a1^b3^d4^e\rbrace$ as a subproblem and work from there? – Ryan Smith Mar 20 '14 at 0:18