2
$\begingroup$

The language is $\{w \mid \text{$w$ is any string except $11$ and $111$}\}$ where the alphabet is $\{0,1\}$.

Drawing the DFA recognizing $\{v \mid \text{$v$ is either $11$ or $111$}\}$, then switching the accept and non-accept states, and finally examining this resulting structure, I thought of it as being:

$(ϵ∪0Σ^*∪1∪10Σ^*∪110Σ^*∪111Σ^+)$

My reasoning was that it has to accept the empty string, or a 0 followed by whatever or just a $1$ or, if it begins with a $1$, a $10$ followed by whatever or, if it begins with $11$, then a $110$ followed by whatever or a $111$ followed by at least a $0$ or a $1$

Does this appear to be correct? If I'm wrong, could you please tell me why?

Thank you,

$\endgroup$
  • $\begingroup$ You could have written it more compactly, e.g. $\epsilon + 1 + (0 + 1(\epsilon + 1 + 11)0)(1 + 0)^*$, but the idea is basically the same. $\endgroup$ – wvxvw Sep 29 '15 at 23:25
  • 4
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Sep 29 '15 at 23:28
2
$\begingroup$

Yes, your idea is correct.
Basically here two things are happening.

  1. Regular languages are closed under compliment operation
  2. If L1 is accepted by DFA1 and DFA2 is obtained by interchanging the final states to non-final states and non-final states to final states of DFA1 then the language accepted by DFA2 is compliment of L1. That is, if
    • DFA1 is a quintuple (Q, Σ, δ , q0, F)
      And L1 is language accepted by DFA1
    • DFA2 is (Q, Σ, δ , q0, (Q - F))
      And L2 is language accepted by DFA2

      Then L2 is compliment of L1.

In this case the languages
L1 = {w∣w is any string except 11 and 111} and L2 = {v∣v is either 11 or 111} are compliment o each other .
Hence your approach is correct.

$\endgroup$

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.