Let $L$ be the language $\{\langle M \rangle : M\text{ is a DFA that accepts only odd-length strings}\}$.

Prove that $L$ is decidable.

How wrong is my answer?

Create a TM $T$ that decides $L$:

  1. Create an equivalent input string $v$ that is in the language $L(M)$.

  2. Give encoding to $T = \langle M, v \rangle$.

  3. TM $T$ simulates $M$ on input $v$.

  4. If TM $T$ halts and accepts, accept. Otherwise, reject.

I would like to know how off I am with my answer.

  • $\begingroup$ I cannot follow your answer, so I'd say it's pretty well off. That said, we don't check answers here. I suggest contacting your TA. $\endgroup$ – Yuval Filmus Nov 30 '16 at 21:55
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Dec 2 '16 at 20:40
  • $\begingroup$ Cross-posted: cs.stackexchange.com/q/66725/755, stackoverflow.com/q/40898210/781723. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. By the way, you might find meta.cs.stackexchange.com/q/1284/755 helpful. $\endgroup$ – D.W. Dec 8 '16 at 3:50

Every DFA can be simplified by a Turing Machine, so you can simplify the DFA you receive as input and compare it to the simplified DFA that accepts odd-length strings.

On input $M$:

  1. Simplify $M$. Remove every unreachable state and transition from $M$ (disjoint from start state)
  2. If the start state of $M$ is reject, and the only other state in $M$ is accept, and for every $w \in \Gamma, \exists$ a $w-arrow$ from accept to reject and from reject to accept, then accept. Otherwise reject.

Forget TMs here, all you need is a decision algorithm, so do this

  1. Create a DFA, $N$ that accepts only odd-length strings (a two-state DFA will do it).
  2. On input $M$, determine whether $L(M)=L(N)$, using known results about regular language closure properties (for example, for any sets $A, B$ we know $A=B$ if and only if their symmetric difference, $(A\cap \overline{B})\cup (\overline{A}\cap B)$ is empty). If $A, B$ are regular, then their symmetric difference is regular (by closure properties of regular languages).
  3. Test the symmetric difference for emptiness. There's a well-known result about how to do that for regular languages.
  4. If the difference is empty, answer "yes" else answer "no".

There's your decider.


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