World's most popular travel blog for travel bloggers.

[Solved]: Turing Machine construction

, , No Comments
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.

Asked By : user3552506

Answered By : kirelagin

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42279

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback