$1.\: A_{DFA} = \{\langle B, w \rangle \mid B \text{ is a } DFA \text{ that accepts input string } w \}$ $2.\:A_{DFA} = \{\langle B \rangle \mid B \text{ is a } DFA \text{ that accepts input string } w \}$

I know how to proof that 1 is decidable by constructing a machine that always halts and accepts whenever $B$ accepts, otherwise rejects. what's the difference between 1 and 2. I find that it doesn't make sense to not include $w$ inside the encoding brackets but I have seen this notation in other places. are they both the same?


The languages are not the same.

In the first one, $w$ is a part of the input.

In the second one, $w$ is fixed beforehand, and the language has to depend on what you fix it to be.

  • $\begingroup$ Will that affect the proof that $A_{DFA}$ is decidable. by other means, How is it possible to proof that a language is decidable if $w$ is not part of the input? $\endgroup$
    – abeer00
    Apr 11 at 19:08
  • $\begingroup$ It definitely can only help if $w$ is fixed beforehand and is not a part of the input, but in any case both languages are decidable since we can emulate the DFA until it halts (and it always halts) $\endgroup$
    – nir shahar
    Apr 11 at 22:12

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.