# Turing Machine construction

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.

• 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. – David Richerby May 7 '15 at 19:26
• Also, remember that $x ≤ y ≤z$ is an abbreviation of $x ≤ y \land y ≤ z$. I bet you can solve these two problems separately. – André Souza Lemos May 7 '15 at 20:59

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$.