[Solved]: Complements of Linear Bounded Automata?

Problem Detail: 

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.

Asked By : IABP

Answered By : Kevin G

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')$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/17898

 Ask a Question

 Download Related Notes/Documents