World's most popular travel blog for travel bloggers.

# [Solved]: Turing Machine construction

, ,
Problem Detail:

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.

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