2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Shaull Nov 22 '14 at 17:30
  • $\begingroup$ 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? $\endgroup$ – MannfromReno Nov 22 '14 at 17:54
  • $\begingroup$ Not really, because you don't get the odd word as input... You have to decide if it exists. $\endgroup$ – Shaull Nov 22 '14 at 18:08
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.