0
$\begingroup$

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 | ε

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ They are allowed to be equal, but not required to be. $\endgroup$ – Yuval Filmus Mar 1 '16 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$ – Shreesh Mar 1 '16 at 14:14
  • $\begingroup$ @Shreesh for that simpler language, would S --> 01 | 0S1 | ε ? $\endgroup$ – user3295674 Mar 1 '16 at 14:20
0
$\begingroup$

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$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.