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


1 Answer 1


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.

  • $\begingroup$ 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? $\endgroup$
    – Ryan Smith
    Commented Mar 20, 2014 at 0:18

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.