120videosEasy Theory
40.7K subscribers on YouTube
Shorts, livestreams, trailers and promos are never listed. Unless a curator approved this channel in full, only individually picked videos appear.
Playlists · 18
120videos
40videosPumping Lemma Proofs (Regular + Context-Free) - Easy Theory
Easy TheoryPlaylist · 40 videos · 10 h 50 min
All 18 playlists
- Reducibility - Easy Theory · 11 videos
- Sipser Textbook Solutions - Easy Theory · 11 videos
- Background Material - Easy Theory · 9 videos
- Context-Sensitive Languages (CSLs) - Easy Theory · 6 videos
- Analysis of Popular Theory Videos/Articles - Easy Theory · 4 videos
- Essence of Theory of Computing - Easy Theory · 3 videos
17:18
24:21Context Free Grammar to Pushdown Automaton Conversion (CFG to PDA)
102K viewsConverting a context-free grammar into an equivalent pushdown automaton.
44:11Context-Free Grammars (CFGs): 15 Examples
71.1K viewsFifteen worked examples of designing context-free grammars.
31:30Cook-Levin Theorem: Full Proof (SAT is NP-complete)
34.8K viewsA full proof of the Cook–Levin theorem: SAT is NP-complete.
22:46Hamiltonian Path is NP-Complete (Directed, Reduction from 3SAT)
53.4K viewsProof that directed Hamiltonian Path is NP-complete by reduction from 3SAT.
29:55Post Correspondence Problem (PCP) is Undecidable Proof
10.5K viewsProof that the Post Correspondence Problem is undecidable.
2:21:21Pumping Lemma for Regular Languages - 20 Examples
220K viewsTwenty worked examples of using the pumping lemma to prove languages are not regular.
19:01Rice's Theorem (Undecidability): 5 Proofs and Examples
24.7K viewsRice's theorem: proof and five examples of undecidable properties of programs.
10:54The Satisfiability Problem, and SAT is in NP
72.2K viewsThe Boolean satisfiability problem and why SAT is in NP.
14:41
19:13Vertex Cover is NP-Complete + Example
47.4K viewsProof that Vertex Cover is NP-complete, with a worked example.
8:56What is a polynomial-time reduction? (NP-Hard + NP-complete)
81.8K viewsWhat polynomial-time reductions are and how they define NP-hard and NP-complete.
18:27"Simple" Computers
A 18-minute video from Easy Theory's catalogue; the title names its topic.
16:01"Simple" Conversions (DFA to NFA to PDA, RG to CFG)
A 16-minute video from Easy Theory's catalogue; the title names its topic.
14:30(Homo)Morphisms vs. Substitutions and Regular Language Closure Properties
A 14-minute video from Easy Theory's catalogue; the title names its topic.
7:390^n 1^n is Not Regular, a Direct Proof
A 8-minute video from Easy Theory's catalogue; the title names its topic.
22:1110 Reasons Why Computer Science Theory is Important
A 22-minute video from Easy Theory's catalogue; the title names its topic.
11:54A Chomsky Normal Form Example (Sipser 2.14 Solution)
A 12-minute video from Easy Theory's catalogue; the title names its topic.
8:27A Cute Research Problem about Context-Free Grammars
A 8-minute video from Easy Theory's catalogue; the title names its topic.
12:23A Double Conversion: Regular Grammar to NFA to Regex!
A 12-minute video from Easy Theory's catalogue; the title names its topic.
8:56A Generalized Pumping Lemma for Regular Languages
A 9-minute video from Easy Theory's catalogue; the title names its topic.
6:39A Stronger Pumping Lemma for Context-Free Languages
A 7-minute video from Easy Theory's catalogue; the title names its topic.
28:26A Very Complicated Way to Divide By 2, but Made Easy
A 28-minute video from Easy Theory's catalogue; the title names its topic.
16:11A Weird Way to Minimize Deterministic Finite Automata
A 16-minute video from Easy Theory's catalogue; the title names its topic.
14:35A nice problem and proof about languages
A 15-minute video from Easy Theory's catalogue; the title names its topic.
18:27A theory question so hard the organizers got it wrong?
A 18-minute video from Easy Theory's catalogue; the title names its topic.
16:35ALL Closure Properties (Regular, CFL, etc.) and Decidability/Undecidability
A 17-minute video from Easy Theory's catalogue; the title names its topic.
3:43ALL_DPDA is Decidable
A 4-minute video from Easy Theory's catalogue; the title names its topic.
9:06Acceptance for Context-Free Grammars is Decidable
A 9-minute video from Easy Theory's catalogue; the title names its topic.
12:25Acceptance for DFAs is Decidable (also, what is a "high-level" description?)
A 12-minute video from Easy Theory's catalogue; the title names its topic.
10:54Acceptance for LBAs is Decidable...but Why?
A 11-minute video from Easy Theory's catalogue; the title names its topic.
9:40Acceptance for NFAs is Decidable (to convert or to not convert? That's the question!)
A 10-minute video from Easy Theory's catalogue; the title names its topic.
4:46Acceptance for Regular Expressions is Decidable
A 5-minute video from Easy Theory's catalogue; the title names its topic.
12:07Acceptance for Turing Machines is Undecidable, but Recognizable
A 12-minute video from Easy Theory's catalogue; the title names its topic.
1:01:44Algorithmic Problem Solving: Intro
A 62-minute video from Easy Theory's catalogue; the title names its topic.
1:28:20Algorithmic Problem Solving: Python Language Features
A 88-minute video from Easy Theory's catalogue; the title names its topic.
Books that go with these videos
As an Amazon Associate, BrighterTube earns from qualifying purchases.