Build NFAs for the following languages:

Question

{w ∈ {0, 1} ∗ | w contains any of the substrings 010, 011 or 1100}, • {w ∈ {0, 1} ∗ | w contains the substrings 010, 011 and 1100}, • {w ∈ {0, 1} ∗ | w has a 0 in the third place}, • {w ∈ {0, 1} ∗ | w has a 0 in the third place from the end}, • {w ∈ {a, b} ∗ | |w| > 2}. • {avb | v ∈ {a, b} ∗}.

Answer 1

In the video, I translate from math to English what each of the six questions is asking. I show a detailed solution to the first and the fourth ones: seeing any of three specific strings, or seeing a zero in a particular spot in the string. In doing so, I talk about the machine "guessing" the right path, which is the heart of non-determinism, and explain epsilon-transitions, where no input is read. These both go away when transforming NFAs to deterministic finite-state automata.

While seeing any of a few strings uses a parallel structure, if you want to make sure you see all of them, as for the second question, you'll want to hook similar structures up in series. Likewise one can re-mix the elements of these two answers to solve the other problems, as well.