Turing Machine for $L$={$a^nb^m: m=n^2, n \geq 1$}

Question

The problem only requires a description of the machine.

I was thinking for each a you need to find 1 + 2k b's where k is the a your on. (ie for the for the first a find 1 bs, the second find 3 bs, fourth find 5 bs, etc). Obviously this is not the way to do it since you need to have difference cycles for each number of a's.

Answer 1

Suppose that the input is indeed of the form $a^nb^m$ (without knowing that $n^2=m$). Let us take as alphabet for the machine $\Sigma = \{a,\overline a, b\}$. The following machine decides $L$, with the hypothesis that the input consists of a run of $a$'s followed by a run of $b$'s:

• If the machine reads $a$:
  • Replace $a$ by $\overline a$,
  • Go the beginning of the input,
  • If we read $a$ or $\overline a$, write $b$ on the auxiliary tape and move to the right,
  • as soon as we read a $b$ on the input tape, rewind the tape until we read a character that is not $\overline a$,
  • start over.
• If the machine reads $b$: check that the number of $b$'s to the right of the current position on the input tape is equal to the number of $b$'s on the auxiliary tape.

Assuming the input is $a^nb^m$, the machine tapes will look like the following:

• $\overline aa^{n-1}b^m$ on the input tape, $b^n$ on the auxiliary tape,
• $\overline{aa}a^{n-2}b^m$ on the input tape, $b^nb^n$ on the auxiliary tape,
• ...
• $\overline{a^{n-1}}ab^m$ on the input tape, $b^{n(n-1)}$ on the auxiliary tape,
• $\overline{a^n}b^m$ on the input tape, $b^{n^2}$ on the auxiliary tape.

When rewinding up to the first character that is not $\overline a$, we hit a $b$, so that the checking stage begins. At that point, the machine accepts iff the auxiliary tape and $b^m$ match, i.e., iff we have $m=n^2$.

So this machine works with the hypothesis that the input is indeed of the form $a^nb^m$. It remains to describe a machine that checks whether this is indeed the case, but this is clear enough (even a deterministic finite automaton can do it, no need to use the tapes). Once you have described this automaton, you can couple the two transition functions to obtain a machine that decides $L$.