Planar Machines in Theory
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: • Context Free Grammar to Pushdown Automaton...
GoFundMe: https://www.gofundme.com/f/easy-theor...
Patreon: / easytheoryyt
Fourthwall: https://easy-theory-llc-shop.fourthwa...
Problem Solving channel: @easytheoryprobsolve
Timeline:
0:00 - Intro
1:38 - Planar NFAs
10:00 - Planar PDAs
13:24 - Planar Turing Machines
Easy Theory Website: https://www.easytheory.org
If you like this content, please consider subscribing to my channel: / @easytheory
▶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.