# Define a DFA that accepts all even length binary strings that don't contain the substring “111”?

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!

• 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. – Tom Zych Dec 9 '18 at 19:11

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.