# Context free grammar for $1^n 0^m 1^k 0^p$ where $n+k=m+p$

i need to convert this CFL to CFG

$$L = \{\; 1^n 0^m 1^k 0^p \mid n\ge 2, k,m,p\ge 1, n+k=m+p\;\}$$

I am trying to solve this problem for a few days but i couldn't. Is there anyone to help me? I'm gonna blow my mind..If somebody can help i will be so grateful..

• What did you try? Where did you get stuck? Dec 23, 2021 at 20:24

We want to generate strings of the form $$1^n 0^m 1^k 0^p$$ with the same number of $$0$$ and $$1$$. This language can be generated by distinguishing two cases.

The first approach is to draw a diagram what happens if we keep counting the difference between the numbers of $$0$$ and $$1$$. This difference between the cases is whether the count drops below zero or not.

The two examples correspond to $$1^5 0^3 1^2 0^4 = 1^2\; (1^3 0^3) \; (1^2 0^2) \; 0^2$$ and $$1^2 0^4 1^5 0^3 = (1^2 0^2) (0^2 1^2) (1^3 0^3)$$.

The structure of the diagram indicates which pairs of $$0$$ and $$1$$ can be generated together by the CFG.

Observe that such a diagram more or less represents how a push-down automaton would keep track of the string.

Alternatively we can do the math.

Let us assume here that $$m \ge n$$. This means there is a number $$t$$ such that $$m = n+t$$. Since we want to have $$n+k = m+p = n+t+p$$ we also need $$k= t+p$$.

Thus this string is of the form $$1^n\, 0^m\, 1^k\, 0^p = 1^n\, 0^{n+t}\, 1^{t+p}\, 0^p = 1^n 0^n\; 0^t 1^t\; 1^p 0^p$$.

Strings of this form are easy to generate by a CFG. In constructing that CFG include the requirement that $$n\ge 2$$, and $$k,m,p \ge 1$$.

The case $$m\le n$$ is handled analogously. The two parts of the grammar can be joined in the standard way, using the construction for union of context-free languages. See the reference question.

• i got it thanks sir u really helped so much i was trying the same thing with letter k but i couldn't do it right thanks again Dec 23, 2021 at 20:32
• i generated cfg both m≥n and m≤n cases now what should i do for the final answer combining the two cfgs ? can u help me just one more time plz Dec 23, 2021 at 21:21
• i got it sir thank you so much you helped a lot Dec 24, 2021 at 3:33