# Writing context free grammar

I have the following language:

{0m1n0n1m | m,n ≠ 0}

I was wanting to write Context-free grammar for it. I'm a little confused because the rule doesn't mention that m and n are not equal to each other, so could we treat them in a case as the same?

So could something like

S --> 0S1S0S1S

or

S --> 0101 | 0S10S1 | ε

• They are allowed to be equal, but not required to be. – Yuval Filmus Mar 1 '16 at 14:12
• First try to write CFG for something simpler like $\{1^n0^n | n >0\}$. Then you can try the language in question. – Shreesh Mar 1 '16 at 14:14
• @Shreesh for that simpler language, would S --> 01 | 0S1 | ε ? – user3295674 Mar 1 '16 at 14:20

For simpler language $\{1^n0^n\ | \ n > 0\}$, we can write grammar as $S \rightarrow 1S0\ |\ 10$.
Now we can replace the non-terminal $S$ by $A$. And write context free grammar for the language in the question. $A$ is in the center of $0^m$ and $1^m$. Also remember $m,n > 0$.
$A \rightarrow 1A0 \ | \ 10$
$S \rightarrow 0S1 \ | \ 0A1$