Constructing Turing machine for $L=\{a^n b^m, m\%n=0\}$

Question

As it says in the title I'm struggling with a problem: construct a Turing machine that decides the language $$L= \{a^n b^m |n,m ∈ \mathbb{N} \text{ and }m\%n=0 \text{ (n divisor of m)}\} $$

It's simple for $ a^n b^m $ but i don't know how to check if $m\%n=0$

Answer 1

If you do not want to mark letters, you could also delete the left most $a$ and move it right of the $b$s. On the way, delete one $b$. After $n$ steps you swapped the positions of $a$s and $b$s and are left with $n$ $a$s and $m-n$ $b$s. Now you take the rightmost $a$ and move it left etc. If there are no $b$s left check the following: If $nk = m$ the $a$s will be a connected block of letters, otherwise there will be space between them.

Answer 2

It's simple.

I get your confusion on how to check if m%n=0. Well you actually don't CHECK IT you make a way that validates it. If you know how to make a Turing Machine that reads a^n b^n then everything would be simple. The easiest method is by pairing each letter.

Consider 'aabb' , we will pair each 'a' and 'b' by replacing them with 'n' and 'm' respectively. The first thing the machine would do is to read 'a' and write 'n' in it's place so it becomes 'nabb'. We would turn left until we find a 'b' hence we will make another state let's call it q1. Once it found a letter 'b' it will replace it with 'm' (successful pairing 'namb') transitioning into another state let's call it q2 which turns left until it finds an 'n'. once it finds it will turn to the right and transition to the original state (because we want to find the NEXT 'a'). now in the same way they will pair thus the string becomes 'nnmm' (notice this process will repeat until we ran out of the letter 'a').

Now how does it know that it finished? since it returned to the original state it will turn to the right until it finds an 'm'. we would make another state called q3 which would loop all the 'm' letters 'tell it finds a blank space to transition into the halting state (notice that if it found another 'b' it won't do anything so the string won't be accepted).

If you understand it then you could easily solve the problem you proposed. m is a multiple of n so the process will be repeated by m/n times. Consider 'aabbbb', we will pair the first two a's and b's the same way but rather than stopping after founding a 'b' in state q3 it will, go back and repeat the same process again but in this time it will halt if and only if there's an 'a' which is not paired (notice that there will never be an excess of the letter 'b').

I think you can do the rest by yourself hope I helped breaking it down for you :)