Regular Languages in 4 Hours (DFA, NFA, Regex, Pumping Lemma, all conversions)

This is a livestream teaching everything you need to know about regular languages, from the start to the end. We covered DFAs, NFAs, regular expressions, and the pumping lemma (to help prove some languages are not regular). We also covered the product construction (union of two DFAs), powerset construction (NFA to DFA), regular expression to NFA (Thompson's construction), NFA to regular expression (GNFA method), and two proofs using the pumping lemma. Timestamps: 0:00 - Start of livestream 20:38 - Start of topics 21:45 - Existence of unsolvable problems 23:56 - What is a computer? 25:56 - Restricting to 1 input/output 30:25 - Restricting to 1 bit output 33:00 - What is a "state" of the computer? 34:45 - Assumptions 37:45 - Example 1 44:35 - Example 2 53:00 - DFA definition 1:02:00 - Formal DFA example 1:12:25 - DFA more definitions (computation, etc.) 1:18:30 - Examples of regular languages 1:22:08 - Closure operations 1:25:15 - Regular operations 1:31:23 - Complement operation 1:32:23 - Regular languages closed under complement 1:35:45 - Regular languages closed under union (Product construction) 1:47:30 - Regular languages closed under intersection 1:49:47 - What about concatenation? 1:53:12 - NFA Definition 1:57:15 - NFA closure for regular operations 2:11:00 - Relationship between NFAs and DFAs 2:13:00 - NFA to DFA (Powerset construction) 2:29:10 - Regular expression definition 2:31:24 - Example regexes 2:36:12 - Regex to NFA (Thompson construction) 2:39:45 - Regex to NFA example 2:45:30 - NFA to Regex (GNFA Method) 2:58:00 - NFA to Regex example 3:17:50 - What other strings are accepted? 3:28:50 - Pumping Lemma statement 3:35:00 - Proof that 0^n1^n is not regular 3:41:10 - Proof that perfect squares are not regular ▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.