Deterministic Finite Automaton for a*b*c*

Here we create a DFA with four states for the language abc*. 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.

Patreon: https://www.patreon.com/easytheory

PDF of DFA: https://drive.google.com/open?id=16ezjiSUzO9ULc3RcnCJkAkr2ga6KTRIL Solutions: https://drive.google.com/open?id=1EDd7jRvXhsNePdLQ56KZmzp-EscFT7lY

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

▶ADDITIONAL QUESTIONS◀

1. How do you make a DFA for the COMPLEMENT of abc*?
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?

▶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. ... https://www.youtube.com/watch?v=0P82hNNbQOA