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: 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
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.
Видео Planar Machines in Theory канала Easy Theory
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
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.
Видео Planar Machines in Theory канала Easy Theory
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
How Covering Arrays can Potentially Save Billions in TestingTwo Different Definitions of NP are EquivalentThe Top Reason Why I'm a ProfessorDeterministic Context-Free Languages NOT Closed Under ConcatenationBonus: A Different Ordering of the Chomsky Normal Form Conversion Algorithm?!How to check if a DFA satisfies a specification (SUB_DFA)!Introduction to the Theory of Computation (Full Course)The Hardest Exam Question I've Ever Given...So Far...How to write a Deterministic Finite Automaton formally? Example Conversion👀Context-Free Grammar (CFG) Example: 0*1*A Cute Research Problem about Context-Free GrammarsPumping Lemma for Regular Languages Example: 0ⁿ1ᵐ, n != m (HARD!)DFA Minimization ExampleMath Basics for Theory in Computer ScienceContext-Free Elections (pumping lemma for CFLs proofs too)A nice problem and proof about languagesBusy Beaver #4 Turing Machine SimulationWhat are Quantifiers?Direct Proofs - how do you do it?