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

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.

• I have no idea what you are asking. What do you mean by "recognizable"? What the exact language you want to talk about? The question seems trivial if one notes that DFA encodings are (probably) not regular.
– Raphael
Nov 12 '13 at 17:53

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.