1
$\begingroup$

I think I have worked out a DFA that doesn't accept the substring "111," but I don't know how to account for accepting even length strings. Here is what I have so far. Any help would be greatly appreciated! enter image description here

$\endgroup$
  • 1
    $\begingroup$ I think you would have to keep track of parity. One set of states for an odd number of bits seen, another for an even number. $\endgroup$ – Tom Zych Dec 9 '18 at 19:11
2
$\begingroup$

Keep in mind that DFA has a "finite" memory, each state knows something about what you've read so far.
$A$ remembers that so far, you've read $w0$ for some $w \in \{0,1\}^*$ or $\epsilon$.
$B$ remembers that so far, you've read $w01$ for some $w \in \{0,1\}^*$ or $1$.
and so on...

Now you can duplicate the states to have the following properties:
$A_{even}$ means that so far you've read $w0$ for some $w \in \{0,1\}^*$ or $\epsilon$, and you've read even number of letters.
$A_{odd}$ means that so far you've read $w0$ for some $w \in \{0,1\}^*$, and you've read odd number of letters ($\epsilon$ has even number of letters, so it's not included here).
$B_{even}$ remembers that so far, you've read $w01$ for some $w \in \{0,1\}^*$, and you've read even number of letters.
$B_{odd}$ remembers that so far, you've read $w01$ for some $w \in \{0,1\}^*$ or $1$, and you've read odd number of letters.

And so on.
You need to re-define your transition function and and accept states to match with the definition of these new states

Edit: I misread the question as accepting '111' as a substring, so the definition of A,B that i showed are a bit off, but the answer to your question is similar in concept.

$\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.