Is the language of DFAs which do not accept themselves recognizable?

Question

I understand how a the language of turing machines which do not accept themselves is not recognizable but I'm not sure if the same proof could be used to describe a DFA... i.e a proof by contradiction in which a recognizer M recognizes a TM which does not accept itself on input ...creates a contradiction in which if M accepts then M does not accept itself.

Answer 1

DFAs always terminate, so if you want to check whether a given DFA accepts or rejects a given word (say its representation), just run it on the word. You can even do this in polynomial time.

Answer 2

interesting idea! havent seen this in the literature but maybe its somewhere. what youve asked is a great simpler conceptual stepping stone into more advanced areas of TCS such as undecidability.

in a word: yes! there are multiple ways to do this. for example: choose any enumeration of all the words in the regular language $L$ where $w_i$ is the $i$th word $w_i$ in the language. then change the $i$th single symbol in each word to another symbol in the same alphabet to create $L'$. by diagonalization, $L'$ cannot be regular. this works for all languages that have at least two symbols. also note that in a sense, all regular languages with an arbitrary number of symbols can be "emulated" by an equivalent language of binary strings only.