I have been trying to create an FA for the language.

$\{w \in \{0, 1\}^∗ , |w|= 4 \vee w \text{ contains the substring }01\}$

I created one that accepts words that contain the substring $01$, but I have a hard time finding a solution for the length part.

This is my attempt so far:

enter image description here

Any help is greatly appreciated.

  • $\begingroup$ Do you want a DFA, or is a NFA enough? If so, you just need to add another part which has 4 transitions until a final state. $\endgroup$
    – Nathaniel
    Apr 17, 2021 at 15:12
  • $\begingroup$ Use the product construction. $\endgroup$ Apr 17, 2021 at 15:14
  • $\begingroup$ @Nathaniel I need an NFA. $\endgroup$
    – humphrey
    Apr 17, 2021 at 16:38
  • $\begingroup$ Thanks, @YuvalFilmus, I took your advice and I was able to produce the union for the two FAs. $\endgroup$
    – humphrey
    Apr 17, 2021 at 20:11

1 Answer 1


The easiest way to construct a deterministic automaton for such a language is to use the product construction:

  1. Construct an automaton for all words of length $4$.
  2. Construct an automaton for all words containing the substring $01$.
  3. Use the product construction to construct an automaton for the union.

If you are allowed to use a nondeterministic automaton, then you can replace the product automaton with a "union automaton", that is, add a new initial state and connect to the the initial states of the two automata with $\epsilon$ transitions.


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.