1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Raphael Nov 12 '13 at 17:53
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 2nd thought/test exercise for reader-- maybe this doesnt quite work (show counterexample!) but there is a similar/close construction that does.... might post the new one if someone shows a counterexample or doesnt find the other correct construction.... also wondering if it is in the literature anywhere.... $\endgroup$ – vzn Nov 12 '13 at 6:09

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.