# Language acceptance by DFA

I have some questions regarding acceptance of a language by DFA

1. Whether more that one dfa accept a language
2. Whether a dfa can accept more than one language
-

If you fix a DFA (call it $D$), then there are strings that it accepts, let's call the set of those strings $ACC_D$, and strings which it rejects (which we can call $REJ_D$). Each input string is either accepted or rejected, then it is either in $ACC_D$ or otherwise, it is in $REJ_D$. $$ACC_D \cup REJ_D = \Sigma^*, \quad \text{and} \quad ACC_D \cap REJ_D = \emptyset.$$

The set $ACC_D$ is in fact the "language" that the DFA accepts. So it is clear that there can be only one such language that $D$ accepts. It is the "Largest" such set, since all the strings which are not there must be in $REJ_D$, ie., they are rejected by the DFA.

-
What if that DFA accepts the language and some more? –  user5507 Nov 10 '12 at 2:18
anything it accepts is defined to be the language.. –  Ran G. Nov 10 '12 at 2:19
So is it possible for my DFA to have two final states and accepts two set of languages –  user5507 Nov 10 '12 at 2:36
Good question. You can ask what is the language accepted per final state. However, the common definition talks about being accepted by any one of the final states, with no distinction between them. So the language of the DFA is the union of all the sets that are being accepted by some final state. –  Ran G. Nov 10 '12 at 2:39
If i have a DFA like that (with two final states) can I say that this DFA accepts the first language? In that case my DFA accepts more than one language since it accepts the second language also since it has two final states. I am confused with this –  user5507 Nov 10 '12 at 2:49
1. Yes, there can be many DFAs for a language. Many will be silly though, one way to get another is to add unreachable states to any DFA for the language). It is also possible to have more than one sensible DFA:

These two DFAs both accept $\{a,b\}^{\ast}$.

2. On the other hand each DFA accepts exactly one language (i.e. no DFA accepts zero languages, or two or more languages) .

-