Language acceptance by DFA

Problem Detail: 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
Asked By : user5507

Answered By : Ran G.

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.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6590

Leave a Reply