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


S --> 0101 | 0S10S1 | ε

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

1 Answer 1


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$


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.