I couldn't figure out how to proceed with this question. Preparing for the finals, can someone explain how to do this step by step?
Design a TM, write low level transitions for $\{a^i b^j :i ≤ j ≤ 2i\}$
While there is unmarked a and b
For every a
Mark a Mark b
End for
End while
If there is no unmarked a, // i<j or i=j
if there is unmarked b, // i<j
for every b
mark a
end for
Sadly this is as far as I can go, and I'm quite sure it's also wrong.
Number of a <= number of b, and
Number of b <= 2* number of a
Assume that the input string is aaabbbbb
For every a
Mark a as A
If there is b, mark it as B.
Else reject // j<i for example AAAaBB
End for
If there is no unmarked b, accept //i=j, AAABBBbb now
For every b
Mark b as B
Ifthere is an A, mark it as F
Else reject. //j>= 2i, for example FFFBBBBBBbbb
End for
Accept //j<=2i