I'm having trouble designing a DFA that accepts substrings of both 01 or 10. So far, I have constructed separate DFAs that accept the substrings "01" and "10" respectively.

enter image description here enter image description here

What I'm stuck with is how to get the union of these two DFAs while preserving all the transitions and states. May I please get some help with this? Thank you in advanced.


1 Answer 1


If you think about it, there are only 3 kinds of string not in your language: $$\varepsilon, 00...0 \text{ and } 11...1.$$ So when you read a string, left to right, there are only four states you need to keep track of to decide if you want to accept

  1. I haven't read any characters yet,
  2. I have read a bunch of $0$s,
  3. I have read a bunch of $1$s, or
  4. none of the above.

If you read the last character and are in 1.-3. then you have read one of the strings mentioned above and reject, otherwise accept.

Translating that thought into a DFA you get (try doing it yourself first):

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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