Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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
share|improve this question

2 Answers 2

up vote 1 down vote accepted

To expand Luke's answer for your second question:

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.

share|improve this answer
    
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:

    Two equivalent DFAs both accepting (a|b)*; the obvious single state DFA with a self loop, and a two state DFA where both states accept.

    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) .

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.