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

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"}$

• You need to find whether $M$ accepts a word (not a language, as your post states) of odd length. To solve 1, how about just going over every word and checking? To solve 2, you need to further analyze how a DFA accepts a word. Write what you have tried, and we'll take it from there. – Shaull Nov 22 '14 at 17:30
• Thanks, so the TM would need to take in M as input and will just accept if the word is odd, otherwise reject. I feel like I'm missing a step though, it seems too easy? – MannfromReno Nov 22 '14 at 17:54
• Not really, because you don't get the odd word as input... You have to decide if it exists. – Shaull Nov 22 '14 at 18:08

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.
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.