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)

  • $\begingroup$ Hint: give any algorithm deciding $S$. How much space does it take? $\endgroup$ – Raphael Dec 1 '14 at 12:59

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.

| cite | improve this answer | |
  • 3
    $\begingroup$ Note that you could also just use one counter and start decrementing it when you reach the $b$s. In fact, you can do even better: if you have an extra tape symbol available, you can decide this language in zero extra space by just crossing off $a$s and $b$s in matched pairs. $\endgroup$ – David Richerby Nov 30 '14 at 22:11
  • $\begingroup$ You are right; two counters are used for illustration. One is enough. Of course I also agree with the second statement assuming that we have an extra tape symbol (i.e. a symbol that is guaranteed not to be part of the input). $\endgroup$ – MightyMouse Nov 30 '14 at 22:18
  • 1
    $\begingroup$ @DavidRicherby Your "zero extra space" and "extra tape symbol" might be confusing in the context of log-space. Space complexity counts the space used in the working tape, where the input is not rewritten. $\endgroup$ – Hendrik Jan Dec 1 '14 at 0:46
  • $\begingroup$ @HendrikJan Good point. This is why I try to avoid working at 10pm on Sundays! $\endgroup$ – David Richerby Dec 1 '14 at 0:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.