[Solved]: Turing recognizable & decidable: binary strings with even length. Let A = {(M) | M is a DFA such that L(M) is not the same as EVEN}

Problem Detail: 

Having trouble with this homework problem. In order to show that A is Turing recognizable and decidable.

$\text{EVEN} = \text{binary strings with even length}$

$Let\;A = \{(M) | \,M\; \text{is a DFA such that L(M) is not the same as EVEN}$

1. $\text{Show that A is Turing-recognizable}$
2. $\text{Show that A is decidable}$

So, at first glance it seems we need to just find a word that M accepts that is an odd length binary string. I'm a bit lost at where to start though.

I believe I'd start by using the TM from Theorem 4.1 of Sipser's Introduction to Theory of Computation which states if a DFA is a decidable language we can use Turing machine T to test if it's decidable:

$\text{T = "On input (B,w) where B is a DFA and w is a string:}$

1. $\text{Simulate B on input w}$

2. $\text{If the simulation ends in an accept state - accept, otherwise reject"}$

Asked By : MannfromReno

Answered By : Shaull

The language is clearly recognizable: given a DFA $M$, simulate it, in minlex order, on every word, and see if there is a word $w$ such that $|w|$ is odd, and $w$ is accepted by $M$, or if there exists a word $w$ such that $|w|$ is even, and $w$ is not accepted by $M$. In both cases - accept.

However, this machine doesn't show the decidability of the language.

In order to decide the language, it is easier to proceed as follows: Let $A$ be a DFA that accepts the language EVEN. Fix such a DFA.

Now, given $M$, we need to decide whether $L(M)=L(A)$. If you feel comfortable with automata, you can just say that this is decidable, and that's it.

If you're not that comfortable yet, consider the following: Given two DFAs $B,C$, it is easy to construct a DFA $D$ such that $L(D)=L(B)\cap \overline{L(C)}$, and it is also easy (well, decidable in NLOGSPACE) whether $L(D)=\emptyset$. The latter test is equivalent to deciding whether $L(B)\subseteq L(C)$. Thus, you can decide whether $L(M)\subseteq L(A)$ and $L(A)\subseteq L(M)$, which amounts to deciding whether $L(A)=L(M)$, and you are done.

Best Answer from StackOverflow

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