0
$\begingroup$

I think I understand the theoretical definition of decidable and undecidable languages but I am struggling with their examples.

A(DFA) = {(M, w): M is a deterministic finite automaton that accepts the string w}

A(TM) = {(M, w): M is a turing machine that accepts the string w}

I know that A(DFA) is decidable and A(TM) is not. But, is A(DFA) a subset of A(TM)?

$\endgroup$
  • $\begingroup$ 1. Can you define what you mean by A(.)? Without a definition of that notation, the question is not answerable -- it's not clear what you are asking. 2. What have you tried? What are your thoughts? We don't want to just do your exercise for you; we want to help you understand -- but for that, we need you to show us your attempts. 3. Your title doesn't match the body of the question. Please edit the question to address all of these issues; it can then be considered for re-opening. Thank you! $\endgroup$ – D.W. Apr 30 '16 at 21:42
  • $\begingroup$ I edited the question. Does it fit the guidelines now? $\endgroup$ – user6268553 May 1 '16 at 3:02
4
$\begingroup$

No, A(DFA) is not necessarily a subset of A(TM). When you write "(M, w)" you actually refer to some encoding of M in some alphabet (usually {0,1}). These encodings of DFAs and TMs can be very different.

For a simple example: Let $A_1, A_2, \dots$ be an enumeration of all DFAs, and let $M_1, M_2, \dots$ be an enumeration of all TMs. You could say that you encode $A_i$ as the word $0 \text{bin}(i)$ and $M_i$ as $1 \text{bin}(i)$, where $\text{bin}(i)$ is the binary representation of the number $i$. Then the two langauges you presented are disjunct.

As it seems that this is part of your question: Being a subset and being computationally easier do not relate. Take the set $\Sigma^*$ of all possible words. It is easily decidable (even by a DFA) but every language, even undecidable ones, are subsets of it.

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