Канал: Cesare Spinoso

Tutorial 6 - Running through the L* algorithm

Tutorial 6 - Running through the L* algorithm

Tutorial 7

Tutorial 7

Tutorial 6 - Setting up the active learning automata problem

Tutorial 6 - Setting up the active learning automata problem

Tutorial 6 - Building the observation table

Tutorial 6 - Building the observation table

Tutorial 6 - Motivating learning automata

Tutorial 6 - Motivating learning automata

Lecture 23 - Rice's Theorem

Lecture 23 - Rice's Theorem

Lecture 24 - Undecidable Problems about CFLs - Part 1

Lecture 24 - Undecidable Problems about CFLs - Part 1

Lecture 5 - NFAs=DFAs, NFA+Epsilon

Lecture 5 - NFAs=DFAs, NFA+Epsilon

Lecture 11 - Proving languages are not regular

Lecture 11 - Proving languages are not regular

Lecture 14 - CFL Proof by Induction and Closure Properties

Lecture 14 - CFL Proof by Induction and Closure Properties

Lecture 7 - Part 6

Lecture 7 - Part 6

Lecture 24 - Part 5

Lecture 24 - Part 5

Lecture 18 - Turing Machines

Lecture 18 - Turing Machines

Lecture 9 - Myhill-Nerode Theorem

Lecture 9 - Myhill-Nerode Theorem

Lecture 3 - DFAs

Lecture 3 - DFAs

Lecture 24 - Part 7

Lecture 24 - Part 7

Lecture 26 - Review of reductions + Turing reductions

Lecture 26 - Review of reductions + Turing reductions

Lecture 24 - Part 8

Lecture 24 - Part 8

Lecture 24 - Part 9

Lecture 24 - Part 9

Lecture 25 - Post Correspondence Problem

Lecture 25 - Post Correspondence Problem

Lecture 13 - Intro to CFLs

Lecture 13 - Intro to CFLs

Lecture 2 - Formal Language Theory

Lecture 2 - Formal Language Theory

Lecture 8 - DFA Minimization

Lecture 8 - DFA Minimization

Lecture 24 - Part 6

Lecture 24 - Part 6

Lecture 24 - Part 4

Lecture 24 - Part 4

Lecture 23 - Clarification on the notation of P(L(M))

Lecture 23 - Clarification on the notation of P(L(M))

Lecture 21 - More mapping reduction exercises!

Lecture 21 - More mapping reduction exercises!

Lecture 17 - Pumping Lemma for CFLs

Lecture 17 - Pumping Lemma for CFLs

Lecture 4 - Minimal DFAs and NFAs

Lecture 4 - Minimal DFAs and NFAs

Lecture 24 - Part 3

Lecture 24 - Part 3

Lecture 24 - Part 2

Lecture 24 - Part 2

Lecture 22 - Undecidability hierarchy

Lecture 22 - Undecidability hierarchy

Lecture 16 - Pushdown Automata

Lecture 16 - Pushdown Automata

Lecture 20 - Intro to reductions

Lecture 20 - Intro to reductions

Lecture 6 - Closure Properties Reg Languages

Lecture 6 - Closure Properties Reg Languages

Why is 26 cool!?

Why is 26 cool!?

Lecture 7 - Part 3

Lecture 7 - Part 3

Lecture 3 - Induction - Inductive Step

Lecture 3 - Induction - Inductive Step

Lecture 7 - RexExp - Part 1

Lecture 7 - RexExp - Part 1

Lecture 7 - Part 2

Lecture 7 - Part 2

Lecture 3 - Review of P(M,w)

Lecture 3 - Review of P(M,w)

Lecture 3 - Induction - Base Case

Lecture 3 - Induction - Base Case

Lecture 7 - Part 4

Lecture 7 - Part 4

Lecture 7 - Part 5

Lecture 7 - Part 5

Why is 25 cool!?

Why is 25 cool!?

Is a^nb^l, l divides n regular?

Is a^nb^l, l divides n regular?

Intuitions for the pumping lemma - What is a "non-regular" language?

Intuitions for the pumping lemma - What is a "non-regular" language?

Is w1cw2 where w1 != w2 regular?

Is w1cw2 where w1 != w2 regular?

Proving a^nb^n n greater 335 is not regular

Proving a^nb^n n greater 335 is not regular

Proving w n0 greater n1 is not regular

Proving w n0 greater n1 is not regular

Proving a^nb^n is not regular

Proving a^nb^n is not regular

Using the closure properties to prove non-regularity

Using the closure properties to prove non-regularity

$Is a^2n union a^{2^n} regular?$

Is a^2n union a^{2^n} regular?

Is w, na + nb = 4nb regular?

Is w, na + nb = 4nb regular?

Proving a^k k perfect cube is not regular

Proving a^k k perfect cube is not regular

Proving 0^n1^j n greater j is not regular

Proving 0^n1^j n greater j is not regular

Using the pumping lemma to prove non-regularity - Playing a game

Using the pumping lemma to prove non-regularity - Playing a game

Presenting the pumping lemma - Intuition and formal statement

Presenting the pumping lemma - Intuition and formal statement

Converting FAs to regular expressions

Converting FAs to regular expressions

Creating regular expression for w contains 101 as a substring

Creating regular expression for w contains 101 as a substring

Converting regular expressions to FAs

Converting regular expressions to FAs

Find an NFA from the regular expression (abb)* + (a*bb*)

Find an NFA from the regular expression (abb)* + (abb)

Regular expression for vwv, |v| = 2

Regular expression for vwv, |v| = 2

Regular expression for w even and odd length

Regular expression for w even and odd length

Shortest string in a language denoted by a regexp - L(r1) + L(a(ba)*)

Shortest string in a language denoted by a regexp - L(r1) + L(a(ba)*)

Strings of length 3 or less in L((0+01)(1+11)*)

Strings of length 3 or less in L((0+01)(1+11)*)

Regular Expressions Introduction

Regular Expressions Introduction

Language denoted by (a+bb)(ab)*

Language denoted by (a+bb)(ab)*

Proving that a DFA must have at least 6 states to accept a particular language

Proving that a DFA must have at least 6 states to accept a particular language

Motivating Minimal DFAs

Motivating Minimal DFAs

DFA that accepts strings with at most one a + Proof of correctness

DFA that accepts strings with at most one a + Proof of correctness

Proving that regular languages are closed under the union (In-depth)

Proving that regular languages are closed under the union (In-depth)

Proving that regular languages are closed under the shuffle operation

Proving that regular languages are closed under the shuffle operation

Proving that regular languages are closed under the reversal

Proving that regular languages are closed under the reversal

Introduction to closure properties (for regular languages)

Introduction to closure properties (for regular languages)

Using the closure properties + Example with interserction

Using the closure properties + Example with interserction

Proving that regular languages are closed under the complement

Proving that regular languages are closed under the complement

Proving that regular languages are closed under concatenation

Proving that regular languages are closed under concatenation

Proving that regular languages are closed under the "star" operation

Proving that regular languages are closed under the "star" operation

Proving that a (particular) combination of sub-languages is regular

Proving that a (particular) combination of sub-languages is regular

Proving that a^nb^n, n less than 42 is regular

Proving that a^nb^n, n less than 42 is regular

Proving that append1(L) is regular

Proving that append1(L) is regular

NFAs - Equivalence of NFAs and DFAs Theorem

NFAs - Equivalence of NFAs and DFAs Theorem

NFAs - NFA to DFA Exercise

NFAs - NFA to DFA Exercise

NFAs - Creating an NFA to accept a language

NFAs - Creating an NFA to accept a language

NFAs - NFA to DFA Conversion Algorithm

NFAs - NFA to DFA Conversion Algorithm

NFAs - Walking through the computation of an NFA

NFAs - Walking through the computation of an NFA

NFAs - Converting an NFA to a DFA Intuitions

NFAs - Converting an NFA to a DFA Intuitions

NFAs - Determining the language accepted by an NFA

NFAs - Determining the language accepted by an NFA

NFAs - Introduction

NFAs - Introduction

Proof Technique - Using the pigenohole principle

Proof Technique - Using the pigenohole principle

Proof Technique - Using induction to prove a statement on trees

Proof Technique - Using induction to prove a statement on trees

Proof Technique - The Pigeonhole Principle

Proof Technique - The Pigeonhole Principle

Proof Technique - Mathematical Induction

Proof Technique - Mathematical Induction

Proving the Myhill-Nerode Theorem (1) implies (2)

Proving the Myhill-Nerode Theorem (1) implies (2)

Uniqueness of minimal DFAs - Myhill-Nerode

Uniqueness of minimal DFAs - Myhill-Nerode

Using M-N to prove that a language is not regular - Myhill-Nerode

Using M-N to prove that a language is not regular - Myhill-Nerode

Proving the Myhill-Nerode theorem (3) implies (1)

Proving the Myhill-Nerode theorem (3) implies (1)

The Myhill-Nerode Theorem

The Myhill-Nerode Theorem

Reminders and definitions - Myhill-Nerode

Reminders and definitions - Myhill-Nerode

Proving the Myhill-Nerode Theorem (2) implies (3)

Proving the Myhill-Nerode Theorem (2) implies (3)

DFA Minimization Algorithm - Introduction and intuition

DFA Minimization Algorithm - Introduction and intuition

DFA Minimization Algorithm - Example

DFA Minimization Algorithm - Example

DFA Exercise - Strings starting with 01 and ending with 10

DFA Exercise - Strings starting with 01 and ending with 10

DFA Exercise - Strings w such that n0(w) + 2*n1(w) mod 5 = 0

DFA Exercise - Strings w such that n0(w) + 2*n1(w) mod 5 = 0

DFA Exercise - The set of all strings, the empty set and the set only containing the emty string

DFA Exercise - The set of all strings, the empty set and the set only containing the emty string

DFA Exercise - Strings containing three 0s and at least two 1s

DFA Exercise - Strings containing three 0s and at least two 1s

DFA Exercise - Strings containing even number of a's and odd number of b's

DFA Exercise - Strings containing even number of a's and odd number of b's

DFA Exercise - Strings with an even number of 1s

DFA Exercise - Strings with an even number of 1s

DFA Exercise - Strings not containing 01

DFA Exercise - Strings not containing 01

DFAs - Visualizing DFA computations and creating DFAs

DFAs - Visualizing DFA computations and creating DFAs

DFAs - Regular Languages

DFAs - Regular Languages

DFAs - Definition

DFAs - Definition

Languages - Operations on languages

Languages - Operations on languages

Languages - Definitions and Properties

Languages - Definitions and Properties

Graph Theory - Definitions and Properties

Graph Theory - Definitions and Properties

Proof Technique - Proof by construction

Proof Technique - Proof by construction

Proof Technique - Proof by contradiction

Proof Technique - Proof by contradiction

Proof Techniques - Proving set equality

Proof Techniques - Proving set equality

Set Theory - Set Operations

Set Theory - Set Operations

Set Theory - Definitions and Properties

Set Theory - Definitions and Properties

Introduction to Theory of Computation Tutorial Series

Introduction to Theory of Computation Tutorial Series

Why is 24 cool!?

Why is 24 cool!?

Miterm Review

Miterm Review

Tutorial 12 - Turing Machines

Tutorial 12 - Turing Machines

Tutorial 9 - Grammar Simplification and Normal Forms

Tutorial 9 - Grammar Simplification and Normal Forms

Tutorial 10 - Pushdown Automata

Tutorial 10 - Pushdown Automata

Tutorial 11 - Pumping Lemma for CFLs

Tutorial 11 - Pumping Lemma for CFLs

Tutorial 8 - CFGs

Tutorial 8 - CFGs

Tutorial 3 - DFAs

Tutorial 3 - DFAs

Tutorial 6 - Grammar

Tutorial 6 - Grammar

Tutorial 4 - NFAs

Tutorial 4 - NFAs

Tutorial 7 - Pumping Lemma

Tutorial 7 - Pumping Lemma

Tutorial 5 - Regular Expressions

Tutorial 5 - Regular Expressions

Tutorial 2 - Languages

Tutorial 2 - Languages

Tutorial 1 - Review of Set Theory

Tutorial 1 - Review of Set Theory

Tutorial 3 - Extra Exercise

Tutorial 3 - Extra Exercise

Final Review (After Midterm)

Final Review (After Midterm)

Final Review (Before Midterm Material)

Final Review (Before Midterm Material)

Final Review Extra Q&As

Final Review Extra Q&As

Tutorial 6 - FAs and Grammars, The Pumping Lemma

Tutorial 6 - FAs and Grammars, The Pumping Lemma

Tutorial 5 - FAs, Rex, Regular Grammars

Tutorial 5 - FAs, Rex, Regular Grammars

Tutorial 2 - Extra DFA exercise

Tutorial 2 - Extra DFA exercise

Tutorial 4 - Closure properties of regular languages & Regular expressions

Tutorial 4 - Closure properties of regular languages & Regular expressions

Tutorial 3 - NFAs

Tutorial 3 - NFAs

Tutorial 7 - Proving a language is not regular, Context-Free grammars

Tutorial 7 - Proving a language is not regular, Context-Free grammars

Tutorial 3 - Conclusion

Tutorial 3 - Conclusion

Tutorial 2 - JFLAP Demo

Tutorial 2 - JFLAP Demo

Tutorial 9 - Push Down Automata (PDAs)

Tutorial 9 - Push Down Automata (PDAs)

Tutorial 3 - NFA to DFA conversion

Tutorial 3 - NFA to DFA conversion

Tutorial 9 - Grammar simplification, Chomsky Normal Form (CNF), Greibach Normal Formal (GNF)

Tutorial 9 - Grammar simplification, Chomsky Normal Form (CNF), Greibach Normal Formal (GNF)

Tutorial 3 - Minimal DFA

Tutorial 3 - Minimal DFA

Tutorial 2 - Introductions to DFAs and Regular languages

Tutorial 2 - Introductions to DFAs and Regular languages

Tutorial 11 - Pumping Lemma for Context-Free languages, Intro to Turing Machines

Tutorial 11 - Pumping Lemma for Context-Free languages, Intro to Turing Machines

Tutorial 8 - Context free grammars, derivation order, ambiguity

Tutorial 8 - Context free grammars, derivation order, ambiguity

Tutorial 12 - Turing Machines

Tutorial 12 - Turing Machines

Tutorial 1 - Review of set theory and introduction to languages

Tutorial 1 - Review of set theory and introduction to languages

Tutorial 11 - Pumping Lemma for CFL

Tutorial 11 - Pumping Lemma for CFL

Tutorial 12 - Turing Machines

Tutorial 12 - Turing Machines

Tutorial 10 - More PDAs and Closure properties CFL

Tutorial 10 - More PDAs and Closure properties CFL

Tutorial 9 - More NPDAs and CFG to PDAs algorithm

Tutorial 9 - More NPDAs and CFG to PDAs algorithm

Tutorial 8 - Pushdown Automata

Tutorial 8 - Pushdown Automata

Tutorial 3 - Regular Expressions

Tutorial 3 - Regular Expressions

Tutorial 4 - FA to RegExp and Regular Grammars

Tutorial 4 - FA to RegExp and Regular Grammars

Tutorial 1 - Review of Set Theory & Languages

Tutorial 1 - Review of Set Theory & Languages

Tutorial 6 - Pumping Lemma

Tutorial 6 - Pumping Lemma

Tutorial 2 - DFAs

Tutorial 2 - DFAs

Tutorial 7 - Grammar Simplification and Normal forms

Tutorial 7 - Grammar Simplification and Normal forms

Midterm Review

Midterm Review

Cesare Spinoso Live Stream

Cesare Spinoso Live Stream

V as a vector subspace of itself - Another interesting case!

V as a vector subspace of itself - Another interesting case!

The zero vector as a subspace - An interesting case!

The zero vector as a subspace - An interesting case!

Proving (or "disproving") that a subset of P(R) is a subspace

Proving (or "disproving") that a subset of P(R) is a subspace

Show that the subset of P(R) such that def. integral = 0 is a subspace

Show that the subset of P(R) such that def. integral = 0 is a subspace

Vector subspaces - How to prove that something is a subspace

Vector subspaces - How to prove that something is a subspace

Set theory - If A is a subset of B and B is a subset of C, show A is a subset of C

Set theory - If A is a subset of B and B is a subset of C, show A is a subset of C

Vector subspace - What is a vector subspace?

Vector subspace - What is a vector subspace?

Set Theory - What is a set? A subset? How do you show that two sets are equal?

Set Theory - What is a set? A subset? How do you show that two sets are equal?

Pn(R) Vector Space - Another example of vector spaces

Pn(R) Vector Space - Another example of vector spaces

Mmxn(R) Vector Space - Another example of vector spaces

Mmxn(R) Vector Space - Another example of vector spaces

Showing that something is NOT a vector space

Showing that something is NOT a vector space

The vector space R^n - An example of a Vector Space (Plus some proofs)

The vector space R^n - An example of a Vector Space (Plus some proofs)

The definition of a Vector Space - Introduction to Vector Spaces

The definition of a Vector Space - Introduction to Vector Spaces

Proving that T^m(x) = λ^m (x) - Eigenvectors and eigenvalues

Proving that T^m(x) = λ^m (x) - Eigenvectors and eigenvalues

Induction - Divisibility Proof (Proving that 11^(n+1) + 12^(2n-1) is divisible by 133)

Induction - Divisibility Proof (Proving that 11^(n+1) + 12^(2n-1) is divisible by 133)

Induction - Divisibility Proof (Proving that 4^(n+1) + 5^(2n-1) is divisible by 21)

Induction - Divisibility Proof (Proving that 4^(n+1) + 5^(2n-1) is divisible by 21)

Induction - Divisibility Proof (Showing n^2 - 1 is divisible by 8)

Induction - Divisibility Proof (Showing n^2 - 1 is divisible by 8)

Induction - Showing that 2^n is greater than n^2

Induction - Showing that 2^n is greater than n^2

Inequality - Proof by induction (Ex 3)

Inequality - Proof by induction (Ex 3)

Induction - Showing that 3^n is less than n!

Induction - Showing that 3^n is less than n!

Summation Induction Proof (More complicated example)

Summation Induction Proof (More complicated example)

Induction - Showing 1^2 + ... + (2n + 1)^2 = (n+1)(2n+1)(2n+3)/3

Induction - Showing 1^2 + ... + (2n + 1)^2 = (n+1)(2n+1)(2n+3)/3

Mathematical Induction (Introduction)

Mathematical Induction (Introduction)

Basis of a subspace (Introduction)

Basis of a subspace (Introduction)

Linear independence and dependence - Prove that e^(rt) and e^(st) are ind.

Linear independence and dependence - Prove that e^(rt) and e^(st) are ind.

Linear independence and dependence (Proof 1)

Linear independence and dependence (Proof 1)

Linear independence and dependence (Examples with R^4 and polynomials)

Linear independence and dependence (Examples with R^4 and polynomials)

Linear independence and dependence (Definition)

Linear independence and dependence (Definition)

Proving that W is a subspace given that W = span (W) (Part 2)

Proving that W is a subspace given that W = span (W) (Part 2)

Proving that span(W) = W given that W is a subspace (Part 1)

Proving that span(W) = W given that W is a subspace (Part 1)