How to Union two Regular Languages with the Product Construction - Easy Theory

Here we create a DFA for the union of the languages of two simple DFAs, using a simple "product" construction of the states of the two machines. We just follow the transitions to form the final DFA, and also noting which states are final. We also check that our answer makes sense at the end.

Whenever you have a problem to solve with DFAs, if you can break it down into "Problem 1 AND Problem 2" or "Problem 1 OR Problem 2", the product construction is your friend. First make the DFAs for each of Problem 1 and Problem 2, and follow the procedure in the video. The final states for either case correspond to intersection for AND, and union for OR.

Recall that a DFA is a 5-tuple (Q, Sigma, delta, q0, F) where Q is the set of states, Sigma is the alphabet, delta is the transition function, q0 is the start state, and F is the set of final state. A computation on a string is the sequence of states that are visited, starting from the start state, on that string. A string is accepted if and only if the computation ends in a final state. In the video, a final state is one with a double circle.

Patreon:   / easytheory  

PDF: https://drive.google.com/open?id=1fjO...
Solutions: https://drive.google.com/open?id=1k1N...

If you like this content, please consider subscribing to my channel:    / @easytheory  

▶ADDITIONAL QUESTIONS◀
1. Is this the smallest DFA for this language?
2. Is there an example of applying the product construction, and every state in the resulting DFA is required?

▶SEND ME THEORY QUESTIONS◀
[email protected]

▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught over 12 courses at Arizona State University, as well as Colgate University, including several sections of undergraduate theory.