May a DFA recognize a language which is a proper subset of the set of all accepted inputs?

For instance, if there is a DFA which decides if an input $W$ has $w_0 = w_n$, can it recognize a language $L$ where there is some $\sigma \in \Sigma$ that does not exist in any element of $L$?

  • $\begingroup$ Can you give a specific example that motivates you to raise this question? It looks like you are concerned with what should be the default setup when we are talking about alphabets and their default embedding into larger alphabets. $\endgroup$ – John L. Jan 28 '19 at 2:46
  • $\begingroup$ I am reading Sipser's Introduction to the Theory of Computation which states that a "$M$ recognizes a language $A$ if $A = \{w | M \text{ accepts } w\}$". It's not clear to me if $A$ must be the set of all inputs which $M$ accepts, or if it need only be a subset of the set of all accepting inputs. Sorry - I should have probably included that in the original question. $\endgroup$ – Aleksandr Jan 28 '19 at 4:04


The language (only one!) recognized by a DFA is the set of all inputs it accepts.

The definition of a DFA also includes its alphabet, so you have to consider that an intrinsic part of the DFA. If you change the alphabet at all, you now have a new and different DFA, which potentially recognizes a different language.

| cite | improve this answer | |

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.