1
$\begingroup$

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.

|cite|improve this question
$\endgroup$

closed as unclear what you're asking by Yuval Filmus, Evil, David Richerby, Juho, Rick Decker Dec 2 '16 at 3:24

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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
0
$\begingroup$

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.
|cite|improve this answer
$\endgroup$
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

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