Here we consider "planar" machines in the undergraduate Theory of Computing class, and whether they are possible to be made, that is, a machine whose drawing does not have edge crossings. We prove that for regular languages, context-free languages, and Turing Machine languages, there is a corresponding "planar" machine. For example, every regular language has a planar NFA. CFG to PDA conversion: https://www.youtube.com/watch?v=GwS__G2M8mU Timeline: 0:00 - Intro 1:38 - Planar NFAs 10:00 - Planar PDAs 13:24 - Planar Turing Machines Easy Theory Website: https://www.easytheory.org Discord: https://discord.gg/SD4U3hs If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 ▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about it. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes. The views expressed in this video are not reflective of any of my current or former employers. ... https://www.youtube.com/watch?v=IlZgqqEXoOU

Here we do an example of the NFA to DFA conversion, otherwise known as the "powerset construction", which solves problem 1.17 in the Sipser textbook. The problem first asks to create an NFA for the given regex, which is easy enough to do. Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are below. Names are listed in alphabetical order by surname. Platinum: Micah Wood Silver: Simone Glinz, Timmy Gy, Josh Hibschman, Patrik Keinonen, Travis Schnider, and Tao Su Easy Theory Website: https://www.easytheory.org Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join Donation (appears on streams): https://streamlabs.com/easytheory1/tip Paypal: https://paypal.me/easytheory Patreon: https://www.patreon.com/easytheory Discord: https://discord.gg/SD4U3hs Merch: Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122 Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 ▶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 many courses at several different universities, including several sections of undergraduate and graduate theory-level classes. ... https://www.youtube.com/watch?v=SCdsgVT6Ktw

Here we show that the AMBIG_CFG problem is undecidable, which asks if a given context-free grammar is ambiguous. We reduce from the Post correspondence problem. Easy Theory Website: https://www.easytheory.org Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join Donation (appears on streams): https://streamlabs.com/easytheory1/tip Paypal: https://paypal.me/easytheory Patreon: https://www.patreon.com/easytheory Discord: https://discord.gg/SD4U3hs #easytheory Youtube Live Streaming (Sundays) - subscribe for when these occur. Social Media: Facebook Page: https://www.facebook.com/easytheory/ Facebook group: https://www.facebook.com/groups/easytheory/ Twitter: https://twitter.com/EasyTheory Merch: Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122 Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 Gold Supporters: Micah Wood Silver Supporters: Timmy Gy ▶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 many courses at several different universities, including several sections of undergraduate and graduate theory-level classes. ... https://www.youtube.com/watch?v=j_BDMeZI4kk

Here we consider the problem of minimizing the number of states in a deterministic finite automaton (DFA). The key here is to identify pairs of states that are "distinguishable", in the sense that reading any string from both of them eventually will lead to an accept state in one case, and a non-accept state in the other case. Then we build the definition of distinguishable states recursively. We conclude with two examples of DFAs: one where no states can be removed, and another where multiple states can be removed. Timeline: 0:00 - Intro 0:30 - Goals of the Video 1:04 - Distinguishing States Example 4:07 - Distinguishing Strings Example 7:17 - Distinguishing States Definition 9:40 - DFA Minimization Example 1 15:35 - DFA Minimization Example 2 20:18 - Conclusion Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are below. Dolev Abuhazira, Josh Hibschman, Micah Wood, Morgan Jones, Patrik Keinonen, Simone Glinz, Tao Su, Timothy Gorden, unit220, Valentine Eben Easy Theory Website: https://www.easytheory.org Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join Donation (appears on streams): https://streamlabs.com/easytheory1/tip Paypal: https://paypal.me/easytheory Patreon: https://www.patreon.com/easytheory Discord: https://discord.gg/SD4U3hs Merch: Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122 Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 ▶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 many courses at several different universities, including several sections of undergraduate and graduate theory-level classes. ... https://www.youtube.com/watch?v=7W2lSrt8r-0