last week we had a problem from An Introduction to Formal Languages and Automata by Linz.
Explain how a linear bounded automata could be constructed to accept the following languages: (a) L = {a^n : n = m^2, m >= 1}
The book offers very little help on how to solve this problem, and I have been unable to find a good online explanation. If some one could explain how to do this problem or a provide a link to an explanation, it would be appreciated.
Thanks
If $n$ is a square (of $m$), then you can divide the word $a^n$ into $m$ blocks of length $m$. An LBA can guess this $m$ and then test whether the input is $a^{m^2}$ by copying the block of length $m$ exactly $m-1$ times. If the result is equal to the input, then the word is accepted.
If you do not want to use non-determinism, you can start by testing for 1, then 2 and so on until either you arrive at the length of the input (accept) or something longer (reject).