Deterministic Finite Automaton (DFA) Example: a*b*c*

Here we create a DFA with four states for the language a*b*c*. The primary purpose of this example is to show the thought process in directly making a DFA for a given language. There are other techniques, such as the GNFA "regular expression to NFA" conversion, coupled with the "NFA to DFA" (powerset) construction, but this is much simpler (in my opinion).

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.

▶ADDITIONAL QUESTIONS◀
1. How do you make a DFA for the COMPLEMENT of a*b*c*?
2. How do you make a DFA for a+b+c+ (a+ means at least 1 a, etc.)?
3. Is it possible to make a DFA with fewer states than this one?

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

[sarthakvashisth]

this really helped me for my exams nobody had a clear explanation for these types of questions on youtube and after watching this I was able to solve almost any similar question while practicing

[ap]

I have been searching for help for the past 3 hours. This has cleared up all of my confusion. Thank you SO much.

[strz]

Thanks so much, this really helped on my CS exam, was struggling to understand in lectures. This 4-minute vid explained it all.

[uzoogbanufe]

Thank you so much! I hope you're doing amazing. You deserve the world!!!

[JD_Mapes]

Well, that was easy...unlike my 2 hour lecture.

[nooh]

Why we didn't return a to q1 since q1 accepts a's, instead we sent it to dead state ?

[free-palestine]

instead of sending the transition c to q2 could you have just sent it to the dead state?