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}$
- $\text{Show that A is Turing-recognizable}$
- $\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:}$
$\text{Simulate B on input w}$
$\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
0 comments:
Post a Comment
Let us know your responses and feedback