Decide $\{a^nb^n\mid n>0\}$ in log space

Question

Given $S = \{a^n b^n \mid n > 0\}$, show $S$ is deterministically decidable in log space.

Hint: to count up to $n$ you need $\log n$ bits.

This comes from some lecture notes at https://www.cise.ufl.edu/research/OptimaNetSci/slides/ThangSept20.pdf

but they did not show how to prove it. Any ideas? (Was posted in wrong section before)

Answer 1

The hint that you have pretty much solves the problem. Essentially you need two counters; one for a and one for b.

1. If the first occurrence is not an a, you reject.
2. Start counting as. You will encounter n of those, until the end of input, or you find a different character. When you stop reading as, at that point you have n in binary. Essentially, every time you read an a, you simply perform addition in the counter that is used for counting as.
3. If you have reached the end of input, or if the next character is not b, you reject.
4. Start counting bs in the same manner as you were counting as until you reach the end of input or encounter a different character. You will read at most n bs, by checking every time that you read a b if you have read less than n characters. This is again straightforward because the two counters for a and b are in binary. If you read a different character you reject. If you reach the end of input after n bs, then you accept; otherwise reject (there is another character coming up - might even be a b).

Thus, we need O(log(n)) space.