Designing a Turing Machine - low level transitions

192 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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