[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}

ignougroup
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