Turing Machine for $ = \{^n ^ c^{2^{nm}} : n,m\ge 1 \}$

38 Views Asked by At

This question requires high level description of Turing machine.

I found that we are able to solve a^n b^m c^nm by :

Step 1 : crossing out one a

Step 2 : continue to cross out one b followed by one c once until b are all crossed out.

Step 3 : we restore all the b's and continue looping until all a's are crossed out.

If there is no c left, we accept. Else, reject.

I was thinking if this would be related to the question where c has a power of ( 2 ^nm )?