Mastering DFA Examples: Sigma*, Empty Set, and More Explained 🤖

Here we try to make sense out of various languages, and more importantly, DFAs. The languages we look at, and make DFAs for, are:
1. Sigma*
2. {epsilon}
3. empty set
4. Sigma* \ {epsilon}
5. (empty set)*
6. {epsilon}*

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.

PDF of DFA: https://drive.google.com/open?id=1JHGVos8VmoQ5oKjlHYeNc2scakx37tDX
Solutions: https://drive.google.com/open?id=1Kto3JbXLNCI2ONxQ8coTnJ3NbYlK4eKx

If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1

▶ADDITIONAL QUESTIONS◀
1. Are these the smallest DFAs for these languages?
2. Is there a set S, not equal to Sigma, where S* = Sigma*?
3. Can we have two DFAs with a different number of states with the same language?

▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com

▶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.