2
$\begingroup$

Would switching the accept and reject states of an LBA A create a new LBA we'll say A' in which the language of A' is the complement of the language of A? I believe the answer is yes just by working out an example...but I'm not sure on a solid proof...nor am I sure if the fact that I am working with an LBA vs a regular turing machine makes a difference in this case.

$\endgroup$
3
  • $\begingroup$ As is often the case, the answer likely depends on the exact definition. What is the acceptance criterion resp. how is the output defined? $\endgroup$
    – Raphael
    Nov 11, 2013 at 15:42
  • $\begingroup$ @Raphael I'm not sure I understand the comment. Isn't the meaning of LBA acceptance well defined? $\endgroup$
    – Kevin G
    Nov 20, 2013 at 21:19
  • $\begingroup$ @KevinG Well-defined, yes, but in multiple variants, all equivalent. For instance, you may allow $c|x|$ cells to be used, or only $|x$. You may consider the whole tape the output, or just everything to the right of the head. You may require the automaton to loop on non-acceptance, or just to stop in a specific final state. Same power, but different technical details. $\endgroup$
    – Raphael
    Nov 21, 2013 at 12:34

2 Answers 2

2
$\begingroup$

I agree with Hendrick Jan; I don't think the currently accepted answer is correct. Even though $A_{LBA}$ is decidable, that doesn't mean the LBA itself doesn't loop.

As a counterexample, consider an LBA $A$ over $\Sigma = \{0, 1\}$, where $A$ accepts $0$ but loops on $1$. Then $L(A) = \{ 0 \}$. The LBA with swapped states, $A'$, would reject $0$ and still loop on $1$, so $L(A') = \{ \}$. This should be a sufficient counterexample as $\overline{L(A)} = \{1\}$, which is not equal to $L(A')$.

$\endgroup$
1
  • $\begingroup$ I checked with my professor, you and Hendrick Jan are correct. $\endgroup$
    – IABP
    Nov 22, 2013 at 3:46
5
$\begingroup$

It depends whether the automaton is deterministic or not. If it is deterministic, then the answer should be yes, just as in the case of DFAs, and you can mimic the proof for DFAs. If it is non-deterministic, then the answer should be no, just as in the case of NFAs; in fact NFAs are a special case of non-deterministic LBAs, and the NFA counterexample can be adapted to the LBA setting.

(The set of languages accepted by non-deterministic LBAs is closed under complementation, but the proof is not quite as straightforward; it is known as the Immerman--Szelepcsényi theorem.)

$\endgroup$
3
  • 2
    $\begingroup$ Probably it is not that easy. Even a deterministic LBA might reject its input by starting an infinite computation. So, we should start by showing we can assume our DLBA to be always halting. $\endgroup$ Nov 11, 2013 at 14:03
  • $\begingroup$ I believe that Yuval's answer is sufficient (I am talking about a deterministic LBA) since we can safely assume that an "infinite computation" would halt since LBA's have a finite number of configurations. $\endgroup$
    – IABP
    Nov 11, 2013 at 16:55
  • 1
    $\begingroup$ Let me explain my point. Assume I start with a DLBA and want to construct a DLBA for its complement language. Swapping accepting and non-accepting states results in a situation where strings with computations that do not halt are not accepted in either of the two DLBA. That is not complement. Indeed the number of configurations is bounded, but you cannot assume without further explanations that the construction exploits this fact. Tou need a solid construction to ensure always halting. Hence you cannot compare this to the case of DFAs. I repeat: "it is not that easy". $\endgroup$ Nov 11, 2013 at 23:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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