Decidable Language Example: Understanding THREE_DFA and Its Significance 🧠

Here we look at the language THREE_DFA, which is the set of all DFAs that accept at most three strings. This is related to the language INFINITE_DFA in that it helps us solve the problem. If the DFA does not accept infinitely many strings, then we can brute force through all possible remaining strings (at most the number of states - 1 in length), and then count the number of accepted strings. If you can solve this a different way, I would love to know about it!

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

▶ADDITIONAL QUESTIONS◀
1. What is the time complexity of this method in solving THREE_DFA?
2. If instead we asked ONE_DFA (i.e., all DFAs accepting at most one string), is there any structure within the DFA we can assume or try to find?

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