Theory of Computing

Table of contents

Title

Pumping Lemma - 1

Pumping Lemma - 2

Pumping Lemma - 3

Pumping Lemma - 4

Pumping Lemma - 5

Pumping Lemma - 6

Use of PL - 1

Use of PL - 2

Examples: PL - 1.1

Examples: PL - 1.2

Additional Examples

PL Cartoon

Closure - Union

Closure Concatenation

Addl Closure Properties

Ex: Complement

Ex: Intersection

Reversal

Substitution

Fig Substitution

Homomorphisms

Fig Homomorphism

Inverse Homomorphism

Theorem 4.16

Theorem 4.16 - Proof concept

Decision: Conversion Algos - 1

Decision: Conversion Algos - 2

Decision: Emptiness

Decision: Membership

Equivalence of States

Example State Equivalence

Table-filling Algorithm

Example Table-filling

Thm 4.20 & RL equivalence

Example RL equivalence

Minimization of DFAs

Example DFA Minimization - 1

Example DFA Minimization - 2

DFA min Theorems

DFA minimization algorithm

Theorem 4.26

Author: Dr. J

E-mail: Juliano@ecst.csuChico.edu

Homepage: http://www.ecst.csuchico.edu/~juliano

Further information:
Computer Science @ California State University, Chico