I have been starting to learn about CFGs and PDAs and have gotten familiar with

Question

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

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 ightarrow AB$

$A ightarrow 0A4|C|D$

$B ightarrow B5|epsilon $

$C ightarrow 0C3|E$

$D ightarrow 1D4|E$

$E ightarrow 1E3|F$

$F ightarrow 2F|epsilon$.

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.