0
$\begingroup$

How should I go about building a Turing machine for the following language:

$$L = \{ a^ib^j \in (a,b)^* \mid i \le j \le 2i \} $$

I know how to construct a Turing machine for $\{ a^nb^nc^n \mid n \in \mathbb N \}$ but don't really where to start for the one above.

$\endgroup$
  • 3
    $\begingroup$ Think about it as a programming problem, first. How would you write a program to accept this language if the only thing you can do is move a cursor around the string and rewrite characters? For example, you could decide $a^nb^nc^n$ by repeatedly crossing out one each of the $a$s, $b$s and $c$s and checking that you run out of all of them at the same time. $\endgroup$ – David Richerby May 7 '15 at 19:26
  • 2
    $\begingroup$ Also, remember that $x ≤ y ≤z$ is an abbreviation of $x ≤ y \land y ≤ z$. I bet you can solve these two problems separately. $\endgroup$ – André Souza Lemos May 7 '15 at 20:59
2
$\begingroup$

How would you construct a TM for $\{a^i b^j \mid i \le j\}$? Well, the easiest solution is to keep removing letters on both sides until you run out of $a$s or $b$s. At this point you can look at what you are left with and decide whether $i \le j$ was initially true.

Now, what if, instead of removing $a$s, you were moving them somewhere to keep for later use? This way you’d be able to test for $i \le j$ and still have all your $a$s available. By doing something similar with all those saved $a$s and the remaining $b$s you will be able to check the second condition, $j \le 2i$.

$\endgroup$
  • $\begingroup$ This is basically what I did. I crossed each a and b. Then I removed each crossed a to cross a b. Once I removed all the crossed as, if there were still any uncrossed bs then I rejected. If all bs were crossed and there were still any as left, then I also rejected. Thanks for the answer. $\endgroup$ – user3552506 May 10 '15 at 15:33

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.