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
