1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Shaull Jun 21 '13 at 16:32
  • $\begingroup$ 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? :) $\endgroup$ – Isabella Prodoprigora Jun 21 '13 at 17:10
3
$\begingroup$

Explaining intuitively why this language is recursive is easy: it's almost trivial to write a computer program in a high-level programming language (e.g. Java, C) that decides this language. Since TMs can simulate high-level languages, you get the result.

If you need a concrete TM that decides this language, try the following:

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.

If, at any point, something "unexpected" happens, (e.g. you run out of 1s, or have too many 1s), then reject. Otherwise you will end up with an empty tape, at which point you can accept.

$\endgroup$
  • $\begingroup$ 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.. $\endgroup$ – Isabella Prodoprigora Jun 21 '13 at 18:09
  • $\begingroup$ I don't see why you would need to separate cases (RE and coRE). Why not describe a machine that decides the language? That is, a machine that always halts with the correct answer. $\endgroup$ – Shaull Jun 21 '13 at 18:14
  • $\begingroup$ @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 $\endgroup$ – Patrick87 Jun 21 '13 at 21:17

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.