# Is the language $0^n 1^n 0^n$ recursive?

I have to find out whether the language $J_1=\{0^n1^n0^n \mid n \in \mathbb{N}\}$ and $J^{c}_{1}$ is recursively enumerable.

I already know that $J_1$ is RE, because I have found Turing machine which accepts $J_1$. I would also like to prove this for $J^{c}_{1}$ by using the following theorem: $J\in RE \wedge J^{c} \in RE \Leftrightarrow J \in Rec$.

So I have to prove that $J_1 \in Rec$. I have already tried but I am stuck. Can anybody please help me?

• RP? Perhaps you mean RE? Also - can you write a java program (or any other language) that decides $J_1$? If so - then it's recursive. Writing an explicit TM is also not difficult, with ~10 states. Jun 21, 2013 at 16:32
• Yes, I meant RE, sorry. I do not know a lot about java.. I have written an explicit TM for $J_1$ but a have to do it also for $J_{1}^{c}$ and here is the problem. I do not know even how to start. Can you please give me a hint? :) Jun 21, 2013 at 17:10

First, erase a 0 and go right until you encounter 1. Replace this 1 with some new symbol $X$. Go back left, and repeat the process until you are out of 0s on the left. Then go back right and do the same thing with the $X$s and 0s on the right.
• Thank you for your answer! I am still not sure if I understand.. I did the similar thing to prove that $J_1 \in RE$. Can I do the same thing for complement-reject when the tape is empty and accept when it si not? Sorry for bothering you.. Jun 21, 2013 at 18:09
• @IsabellaProdoprigora Note also that if $L$ and $L^C$ are both $RE$, then both are recursive. I recently answered a question where I demonstrated this fact: cs.stackexchange.com/a/12749/69 Jun 21, 2013 at 21:17