Канал: Easy Theory

Context-Free Grammars (CFGs): 15 Examples

Context-Free Grammars (CFGs): 15 Examples

Why This All Matters

Why This All Matters

Planar Machines in Theory

Planar Machines in Theory

Fourteen DFA Examples? No Problem!

Fourteen DFA Examples? No Problem!

An Update

An Update

How to Become a Professor #shorts

How to Become a Professor #shorts

This CompSci Video was 100% written by ChatGPT

This CompSci Video was 100% written by ChatGPT

[April Fools] Exponential Lower Bounds for Circuit Families (P ≠ NP)

[April Fools] Exponential Lower Bounds for Circuit Families (P ≠ NP)

Turning 30

Turning 30

wish me luck

wish me luck

ChatGPT vs. Professor's Computer Science Exam

ChatGPT vs. Professor's Computer Science Exam

I proved a math conjecture

I proved a math conjecture

How to Become a Professor in 6 Steps

How to Become a Professor in 6 Steps

All Acronyms for Theory of CS class #shorts

All Acronyms for Theory of CS class #shorts

a student tried to bribe me once

a student tried to bribe me once

The REAL Reason why Math/Humanities aren't "Useless"

The REAL Reason why Math/Humanities aren't "Useless"

I got a scorpion bite before my Ph.D. Defense 🦂

I got a scorpion bite before my Ph.D. Defense 🦂

Top 5 Tips for Theory Computer Science #shorts

Top 5 Tips for Theory Computer Science #shorts

The Top Reason Why I'm a Professor

The Top Reason Why I'm a Professor

Rice's Theorem Example: Emptiness for Turing Machines

Rice's Theorem Example: Emptiness for Turing Machines

Rice's Theorem (Undecidability): 5 Proofs and Examples

Rice's Theorem (Undecidability): 5 Proofs and Examples

Context-Free Grammar (CFG) Example: Non-Palindromes

Context-Free Grammar (CFG) Example: Non-Palindromes

Context-Free Grammar (CFG) Example: Nested Pairs

Context-Free Grammar (CFG) Example: Nested Pairs

Context-Free Grammar (CFG) Example: Equal Pairs

Context-Free Grammar (CFG) Example: Equal Pairs

Context-Free Grammar (CFG) Example: Complement of 0^n1^n2^n

Context-Free Grammar (CFG) Example: Complement of 0^n1^n2^n

$Context-Free Grammar (CFG) Example: {a^i b^j c^k : i at most j+k}$

Context-Free Grammar (CFG) Example: {a^i b^j c^k : i at most j+k}

Context-Free Grammars (CFGs): 5 Intermediate Examples

Context-Free Grammars (CFGs): 5 Intermediate Examples

Context-Free Grammar (CFG) Example: (0 U 1)*

Context-Free Grammar (CFG) Example: (0 U 1)*

Context-Free Grammar (CFG) Example: Union/Concat/Star

Context-Free Grammar (CFG) Example: Union/Concat/Star

Context-Free Grammar (CFG) Example: Palindromes

Context-Free Grammar (CFG) Example: Palindromes

$Context-Free Grammar (CFG) Example: {a^i b^j c^k : i != j}$

Context-Free Grammar (CFG) Example: {a^i b^j c^k : i != j}

Context-Free Grammar (CFG) Example: 0*1*

Context-Free Grammar (CFG) Example: 01

Context-Free Grammars (CFGs): 5 Easy Examples

Context-Free Grammars (CFGs): 5 Easy Examples

Context Free Grammar to Pushdown Automaton Conversion (CFG to PDA)

Context Free Grammar to Pushdown Automaton Conversion (CFG to PDA)

My Favorite Prank I've Pulled #shorts | Professor Dougherty

My Favorite Prank I've Pulled #shorts | Professor Dougherty

Horses and Colors (Induction False "Proof")

Horses and Colors (Induction False "Proof")

Busy Beaver #4 Turing Machine Simulation

Busy Beaver #4 Turing Machine Simulation

How Covering Arrays can Potentially Save Billions in Testing

How Covering Arrays can Potentially Save Billions in Testing

Thanks a million.

Thanks a million.

why I haven't made videos recently #shorts

why I haven't made videos recently #shorts

Turing Machine Example: a^n b^n c^n

Turing Machine Example: a^n b^n c^n

Let's Solve This Research Problem Together.

Let's Solve This Research Problem Together.

Sunday Grading with Ryan

Sunday Grading with Ryan

The Most Amazing Exam Cheating Story

The Most Amazing Exam Cheating Story

A nice problem and proof about languages

A nice problem and proof about languages

My Responses to Why You "Hate" Theoretical Computer Science

My Responses to Why You "Hate" Theoretical Computer Science

My Problem with Pushdown Automata and Turing Machines

My Problem with Pushdown Automata and Turing Machines

10 Reasons NO ONE Should Get a Ph.D.

10 Reasons NO ONE Should Get a Ph.D.

Easy Theory Doesn't Support Academic Integrity Violations...Again

Easy Theory Doesn't Support Academic Integrity Violations...Again

My Students Disproved a Conjecture

My Students Disproved a Conjecture

Real Professor's College Grades 👀

Real Professor's College Grades 👀

The "BEST" Sponsorship Email I've Ever Received

The "BEST" Sponsorship Email I've Ever Received

my next journey

my next journey

This AI Does Your Computer Science Homework...kinda

This AI Does Your Computer Science Homework...kinda

Getting a Ph.D. at 26

Getting a Ph.D. at 26

The First Automaton made with Manim

The First Automaton made with Manim

👀

Why are Turing Machines so powerful?

Why are Turing Machines so powerful?

This Computer Science Paper is (Probably) Hilarious

This Computer Science Paper is (Probably) Hilarious

Thanks for 10,000 Subscribers ❤️ #shorts

Thanks for 10,000 Subscribers ❤️ #shorts

DFA Minimization Algorithm + Example

DFA Minimization Algorithm + Example

What is Theoretical Computer Science?

What is Theoretical Computer Science?

Good Luck in Spring 2022! #shorts

Good Luck in Spring 2022! #shorts

What did you like about theory? #shorts

What did you like about theory? #shorts

End-of-Semester Chill (OpenRCT2)

End-of-Semester Chill (OpenRCT2)

How I Published a Paper in Theoretical Computer Science

How I Published a Paper in Theoretical Computer Science

"I Hate Theory of Computer Science" - why? #shorts

"I Hate Theory of Computer Science" - why? #shorts

Complexity Theory Professors Be Like

Complexity Theory Professors Be Like

Theory Computer Science Professors Be Like (Part 2)

Theory Computer Science Professors Be Like (Part 2)

Livestream: About the “theory professors be like” video 🔴

Livestream: About the “theory professors be like” video 🔴

Theory Computer Science Professors Be Like (Parody)

Theory Computer Science Professors Be Like (Parody)

Simplifying Computers | Essence of Theoretical Computer Science #2

Simplifying Computers | Essence of Theoretical Computer Science #2

Deterministic Finite Automaton to Turing Machine Conversion (DFA to TM)

Deterministic Finite Automaton to Turing Machine Conversion (DFA to TM)

Formal Definitions Theoretical CS 100% Speedrun [World Record]

Formal Definitions Theoretical CS 100% Speedrun [World Record]

Limits of computers | Essence of Theoretical Computer Science #1

Limits of computers | Essence of Theoretical Computer Science #1

Problem Solving Livestream (Turing Machines)

Problem Solving Livestream (Turing Machines)

Problem Solving Session 1 (Context-Free Languages) - Easy Theory

Problem Solving Session 1 (Context-Free Languages) - Easy Theory

Ogden's Lemma for Context-Free Languages Proof

Ogden's Lemma for Context-Free Languages Proof

"Simple" Conversions (DFA to NFA to PDA, RG to CFG)

"Simple" Conversions (DFA to NFA to PDA, RG to CFG)

Celebration of 500k Views - Easy Theory

Celebration of 500k Views - Easy Theory

Regex to NFA Conversion Isn't Hard! (Sipser 1.28a)

Regex to NFA Conversion Isn't Hard! (Sipser 1.28a)

500,000 Views/7500 Subscribers 🥳

500,000 Views/7500 Subscribers 🥳

DFA Example: Binary Multiples of n (Sipser 1.37 Solution)

DFA Example: Binary Multiples of n (Sipser 1.37 Solution)

Problem Solving Livestream #2

Problem Solving Livestream #2

Problem Solving Livestream #1

Problem Solving Livestream #1

What is the NFA to DFA conversion? (Sipser 1.17 Solution)

What is the NFA to DFA conversion? (Sipser 1.17 Solution)

A Chomsky Normal Form Example (Sipser 2.14 Solution)

A Chomsky Normal Form Example (Sipser 2.14 Solution)

Is this Context-Free Grammar ambiguous? (Sipser 2.9 Solution) - Easy Theory

Is this Context-Free Grammar ambiguous? (Sipser 2.9 Solution) - Easy Theory

Algorithmic Problem Solving: Recurrence Relations

Algorithmic Problem Solving: Recurrence Relations

CFG and Parse Tree Examples! (Sipser 2.1 Solution)

CFG and Parse Tree Examples! (Sipser 2.1 Solution)

Algorithmic Problem Solving: What is an Algorithm?

Algorithmic Problem Solving: What is an Algorithm?

Algorithmic Problem Solving: Python Language Features Pt. 2

Algorithmic Problem Solving: Python Language Features Pt. 2

Algorithmic Problem Solving: Python Language Features

Algorithmic Problem Solving: Python Language Features

Algorithmic Problem Solving: Intro

Algorithmic Problem Solving: Intro

Pumping Lemma Example: Non-Palindromes are not Regular - Easy Theory

Pumping Lemma Example: Non-Palindromes are not Regular - Easy Theory

Pumping Lemma Example: Factorials is not Regular

Pumping Lemma Example: Factorials is not Regular

Chomsky Normal Form Conversion Example: Balanced Parentheses

Chomsky Normal Form Conversion Example: Balanced Parentheses

I Now Have This Big White Thing

I Now Have This Big White Thing

DFAs -- Intro Theory of Computation Help Session #1

DFAs -- Intro Theory of Computation Help Session #1

10 Reasons Why Computer Science Theory is Important

10 Reasons Why Computer Science Theory is Important

Pumping Lemma for Regular Languages Example: Powers of 2

Pumping Lemma for Regular Languages Example: Powers of 2

The Polynomial Hierarchy, what is it?

The Polynomial Hierarchy, what is it?

What is the Totally Quantified Boolean Formula (TQBF) problem?

What is the Totally Quantified Boolean Formula (TQBF) problem?

What does PSPACE-Complete even mean?

What does PSPACE-Complete even mean?

Pumping Lemma for Regular Languages Example: 0^m 1^n, m divides n

Pumping Lemma for Regular Languages Example: 0^m 1^n, m divides n

A Stronger Pumping Lemma for Context-Free Languages

A Stronger Pumping Lemma for Context-Free Languages

Channel Update, 1 year later

Channel Update, 1 year later

Does Veritasium's/Hilbert's Infinite Hotel Really Run out of Room?

Does Veritasium's/Hilbert's Infinite Hotel Really Run out of Room?

Randomized Quicksort via Integrals

Randomized Quicksort via Integrals

Hamiltonian Path is NP-Complete (Directed, Reduction from 3SAT)

Hamiltonian Path is NP-Complete (Directed, Reduction from 3SAT)

A Weird Way to Minimize Deterministic Finite Automata

A Weird Way to Minimize Deterministic Finite Automata

The Bellman-Ford Algorithm, what is it?

The Bellman-Ford Algorithm, what is it?

It's Impossible to Deal with So Much Space

It's Impossible to Deal with So Much Space

Cantor's Diagonalization DOES Work

Cantor's Diagonalization DOES Work

What is Dijkstra's Algorithm? - Easy Theory

What is Dijkstra's Algorithm? - Easy Theory

NL-completeness and NL = coNL (Immerman-Szelepcsényi Theorem)

NL-completeness and NL = coNL (Immerman-Szelepcsényi Theorem)

Decidable Languages NOT Closed Under Homomorphism

Decidable Languages NOT Closed Under Homomorphism

Amazon Coding Interview: Is this a Binary Search Tree?

Amazon Coding Interview: Is this a Binary Search Tree?

Rice's Theorem Proof using the Recursion Theorem?! - Easy Theory

Rice's Theorem Proof using the Recursion Theorem?! - Easy Theory

The Recursion Theorem: Proof + Examples

The Recursion Theorem: Proof + Examples

How Accurate is Tom Scott's "Sorting Algorithms and Big O Notation" video?

How Accurate is Tom Scott's "Sorting Algorithms and Big O Notation" video?

Breadth-First Search in a Graph, what is it? - Easy Theory

Breadth-First Search in a Graph, what is it? - Easy Theory

Google Coding Interview Question: Deepest Node in a Binary Tree

Google Coding Interview Question: Deepest Node in a Binary Tree

Logarithmic Space in Complexity Theory

Logarithmic Space in Complexity Theory

Undecidable Language Example: Moving Left Three Times in a Row

Undecidable Language Example: Moving Left Three Times in a Row

How accurate is Tom Scott's "Are There Problems That Computers Can't Solve?" video?

How accurate is Tom Scott's "Are There Problems That Computers Can't Solve?" video?

A theory question so hard the organizers got it wrong?

A theory question so hard the organizers got it wrong?

That Was Easy...Theory

That Was Easy...Theory

How accurate is Veritasium about the Collatz 3x+1 Problem?

How accurate is Veritasium about the Collatz 3x+1 Problem?

Context-Free Grammar (CFG) Example: Empty Set

Context-Free Grammar (CFG) Example: Empty Set

Pumping Lemma for Regular Languages Examples: w#w and ww

Pumping Lemma for Regular Languages Examples: w#w and ww

Savitch's Theorem (Complexity Theory), Statement and Proof

Savitch's Theorem (Complexity Theory), Statement and Proof

What is Space? (for complexity theory) - Easy Theory

What is Space? (for complexity theory) - Easy Theory

What is a Parse Tree? + Example

What is a Parse Tree? + Example

Pumping Lemma for Regular Languages Example: Primes

Pumping Lemma for Regular Languages Example: Primes

Pumping Lemma for Regular Languages Example: Same Number of 00s and 11s

Pumping Lemma for Regular Languages Example: Same Number of 00s and 11s

Pumping Lemma for Regular Languages Example: 0^n 1^m (n is less than 3m)

Pumping Lemma for Regular Languages Example: 0^n 1^m (n is less than 3m)

Pumping Lemma for Regular Languages Example: Perfect Squares

Pumping Lemma for Regular Languages Example: Perfect Squares

Exact "Fast" Algorithm for the Maximum Independent Set Problem

Exact "Fast" Algorithm for the Maximum Independent Set Problem

Pumping Lemma for Regular Languages Example: 0ⁿ10ⁿ

Pumping Lemma for Regular Languages Example: 0ⁿ10ⁿ

Pumping Lemma for Regular Languages Example: 0²ⁿ1ⁿ

Pumping Lemma for Regular Languages Example: 0²ⁿ1ⁿ

Pumping Lemma for Regular Languages Example: More 1s than 0s

Pumping Lemma for Regular Languages Example: More 1s than 0s

Pumping Lemma for Regular Languages Example: 0ⁿ1ᵐ, n != m (HARD!)

Pumping Lemma for Regular Languages Example: 0ⁿ1ᵐ, n != m (HARD!)

Pumping Lemma for Regular Languages Example: Equal 0s and 1s

Pumping Lemma for Regular Languages Example: Equal 0s and 1s

Pumping Lemma for Regular Languages Example: 0ᵐ1ⁿ 0ᵐ+ⁿ and 0ᵐ1ⁿ 0ᵐ*ⁿ

Pumping Lemma for Regular Languages Example: 0ᵐ1ⁿ 0ᵐ+ⁿ and 0ᵐ1ⁿ 0ᵐ*ⁿ

Fast Exponential-Time Algorithms for 3SAT

Fast Exponential-Time Algorithms for 3SAT

Pumping Lemma for Regular Languages Example: 0ⁿ1ⁿ

Pumping Lemma for Regular Languages Example: 0ⁿ1ⁿ

Useless Turing Machines are Undecidable

Useless Turing Machines are Undecidable

Pumping Lemma for Regular Languages TWENTY Examples and Proof Strategies!

Pumping Lemma for Regular Languages TWENTY Examples and Proof Strategies!

Why There's (Likely) No Pumping Lemma for Context-Sensitive Languages

Why There's (Likely) No Pumping Lemma for Context-Sensitive Languages

What is a Context-Sensitive Grammar/Language? + Example

What is a Context-Sensitive Grammar/Language? + Example

A Very Complicated Way to Divide By 2, but Made Easy

A Very Complicated Way to Divide By 2, but Made Easy

Nondeterministic Finite Automata + Powerset Construction | ToC 2019 Lecture #3

Nondeterministic Finite Automata + Powerset Construction | ToC 2019 Lecture #3

Regular Languages Closed Under Union Proof + Example

Regular Languages Closed Under Union Proof + Example

Regular Languages Closed Under Complement Proof

Regular Languages Closed Under Complement Proof

What is a regular language? + Examples

What is a regular language? + Examples

Undecidable Languages NOT Closed Under Concatenation

Undecidable Languages NOT Closed Under Concatenation

Mapping Reductions are Transitive

Mapping Reductions are Transitive

Mapping Reductions are not Always Possible

Mapping Reductions are not Always Possible

How to write a Deterministic Finite Automaton formally? Example Conversion

How to write a Deterministic Finite Automaton formally? Example Conversion

Deterministic Finite Automata, 2 Examples

Deterministic Finite Automata, 2 Examples

"Simple" Computers

"Simple" Computers

Syllabus, Simple Machines, and Deterministic Finite Automata | ToC 2019 Lecture #1

Syllabus, Simple Machines, and Deterministic Finite Automata | ToC 2019 Lecture #1

Is this a context-free language?

Is this a context-free language?

Pumping Lemma for Linear Languages Proof + Example

Pumping Lemma for Linear Languages Proof + Example

How to Not Swear with Regular Languages - Easy Theory

How to Not Swear with Regular Languages - Easy Theory

Context-Free Grammar for Non-Palindromes

Context-Free Grammar for Non-Palindromes

Minimal Context-Free Grammars are Undecidable

Minimal Context-Free Grammars are Undecidable

Busy Beaver Numbers are Undecidable

Busy Beaver Numbers are Undecidable

What is the Time Hierarchy Theorem? - Easy Theory

What is the Time Hierarchy Theorem? - Easy Theory

Verifying Addition is Regular (Sipser Problem 1.32 Solution) - Easy Theory

Verifying Addition is Regular (Sipser Problem 1.32 Solution) - Easy Theory

Vertex Cover is NP-Complete + Example

Vertex Cover is NP-Complete + Example

Finite Changes to Languages Don't Do Anything

Finite Changes to Languages Don't Do Anything

Contractible Strings with TWO Characters is Not Regular (Extra Video)

Contractible Strings with TWO Characters is Not Regular (Extra Video)

Pumping Lemma Example: Contractible Strings (Kinda Hard...)

Pumping Lemma Example: Contractible Strings (Kinda Hard...)

Stuck Ships are Undecidable!

Stuck Ships are Undecidable!

How to Check If Your SHIP is Stuck using a Regex, NFA, and DFA (ToC Problems #14)

How to Check If Your SHIP is Stuck using a Regex, NFA, and DFA (ToC Problems #14)

Pushdown Automaton (PDA) Example: Edit Distance

Pushdown Automaton (PDA) Example: Edit Distance

3SAT is NP-complete Proof

3SAT is NP-complete Proof

A Cute Research Problem about Context-Free Grammars

A Cute Research Problem about Context-Free Grammars

Cook-Levin Theorem: Full Proof (SAT is NP-complete)

Cook-Levin Theorem: Full Proof (SAT is NP-complete)

Why does it take 2n-1 rules to make a string in Chomsky Normal Form?

Why does it take 2n-1 rules to make a string in Chomsky Normal Form?

What is a polynomial-time reduction? (NP-Hard + NP-complete)

What is a polynomial-time reduction? (NP-Hard + NP-complete)

Bonus: A Different Ordering of the Chomsky Normal Form Conversion Algorithm?!

Bonus: A Different Ordering of the Chomsky Normal Form Conversion Algorithm?!

The Satisfiability Problem, and SAT is in NP

The Satisfiability Problem, and SAT is in NP

DFA for Binary Multiples of k

DFA for Binary Multiples of k

Clique and Subset Sum are in NP

Clique and Subset Sum are in NP

DFA for a^m b^n where m+n is even

DFA for a^m b^n where m+n is even

Two Different Definitions of NP are Equivalent

Two Different Definitions of NP are Equivalent

Is this the hardest exam ever? Solutions included!

Is this the hardest exam ever? Solutions included!

Bonus Video: 5 Open Problems about Context-Free Languages - Easy Theory

Bonus Video: 5 Open Problems about Context-Free Languages - Easy Theory

Live Solve of all GATE 2021 Computer Science (CSE) Theory Questions

Live Solve of all GATE 2021 Computer Science (CSE) Theory Questions

Regular/CFLs NOT Closed under Shuffle

Regular/CFLs NOT Closed under Shuffle

Verifiers and Certificates

Verifiers and Certificates

The Hardest Exam Question I've Ever Given...So Far...

The Hardest Exam Question I've Ever Given...So Far...

An Important Point About Nondeterministic Time

An Important Point About Nondeterministic Time

5000 subscribers!!! 🎊 #shorts

5000 subscribers!!! 🎊 #shorts

ALL_DPDA is Decidable

ALL_DPDA is Decidable

Relatively Prime is in P

Relatively Prime is in P

A Generalized Pumping Lemma for Regular Languages

A Generalized Pumping Lemma for Regular Languages