0
$\begingroup$

$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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Apr 11, 2021 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
    Commented Apr 11, 2021 at 22:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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