Turing machine to the languge $\{ a^ib^j | j=2^i \}$

Question

I need to build a deterministic turing machine to the languge:

$L = \{ a^ib^j | j=2^i \}$

I figured that I need to delete one $a$ for every ${2^i}$ $b$ until the tape contains no $a$ or $b$ or both. Then deciding whether the word is in the language is easy.

For example, this will be accepted - $aabbbb$, but this won't - $aaabbbbbb$.

I fail to understand how to change the tape as explained above. I manage to delete $b$ $2i$ times, instead of $2^i$ times.

Answer 1

The machine below assumes the input is a string of $a$'s follows by a string of $b$'s, and the tape otherwise has all $0$'s.

The machine will try to cut the number of $b$'s in half for every $a$. So, when the input is indeed of the form $a^ib^j$ with $j = 2^i$, then when there are no $a$'s left, there should be exactly one $b$ left. If that is indeed the case, it will Accept.

The machine will Reject if it ever gets into one of these conditions:

There are no $a$'s to start with in the first place (so now it is in state $8$), but it finds there are no $b$'s either.

There are no $a$'s left, erased a $b$ (so now it is in state $9$), but finds there are still more $b$'s left.

After the string of $a$'s (now it is in state $1$) it finds there are no $b$'s

To cut the number of $b$'s in half, the machine will erased a $b$ for every $b$ that it replaces with a $c$. If it replaced a $b$ with a $c$ but finds there is no additional $b$ to erase, then that means the number of $b$'s was odd. So, if it ever finds that after at least $a$ was erased (now it is in state 2), then something is amiss.

Especially with this last feature, I think this machine is pretty quick. For example, if it gets as input $aabbbbbbb$, it quickly determines there is an odd number of $b$'s, and will Reject.

Answer 2

This is not quite a proper answer, but a longer comment:

m-tag loops are cool. This may or may not help you, but here's a 2-tag loop that possibly does what you want.

tagloop[<|"a"->"a","b"->"ca","c"->"bb"|>,#]&/@{"aabbbb","aaabbbbbb"}

 -> {{2,{{aabbbb,0},{acccc,0},{abbbb,1},{cccc,0},{bbbb,0}}}
 -> {-1,{{aaabbbbbb,0},{aaaaaaaa,1},{aaaa,1},{aa,1},{a,1}}}}

Answer 3

Here's a Turing machine that recognizes $L= \{a^i b^j \big| \ j = {2^i}\}$ :

• start state if you don't see an $a$, accept iff there's no other character on read band.
  Else write two $1$s in the write band, move writing head to the begining and jump to expansion state.
• expansion state if you see an $a$, double the number of $1$s in the write band, move writing head to the begining and jump to expansion state.
  Else, go to counting state.
• counting state If you read an $a$, reject.
  If you read a $b$ on input band and a $1$ in write band, erase that $1$, move the writing head to the right, then go to counting state.
  If you read a $b$ on input band and no $1$ in write band, reject. If you reached the end of input band, accept if there's no more $1$ on write band, else reject.

Of course this is just a scheme of the machine, but I leave the details to you.