Theory of Computing


Click here to start

Table of contents

Title

Normal Forms for CFGs - 1

Normal Forms for CFGs - 2

Properties of useful symbols

Thm 7.2 - useless symbols

Thm 7.4 - generating symbols

Thm 7.6 - reachable symbols

Elim useless sym - Ex 1

Elim useless sym - Ex 2

Normal Forms for CFGs - 2

Thm 7.7 - nullable

Thm 7.9 - epsilon productions

Eliminate e-prods Ex - 1

Eliminate e-prods Ex - 2

Normal Forms for CFGs - 2

Thm 7.11 - Find unit pairs

Thm 7.13 - elim unit prods

Cleaning up grammars

Chomsky Normal Form

CNF Procedure - 1

CNF Procedure - 2

CNF Procedure - 3

CNF Procedure - 4

Thm 7.16 - CNF and CFG

Pumping Lemma for CFLs

Thm 7.17 PL 4 CFLs - 1

PL 4 CFLs - 2

PL 4 CFLs - 3

PL 4 CFLs - 4

PL 4 CFLs - 5

PL 4 CFLs - 5

PL 4 CFLs - 6

PL 4 CFLs Proof - 1

PL 4 CFLs Proof - 2

Substitutions - 1

Substitutions - 2

Substitutions - 3

Substitution Theorem - 1

Substitution Theorem - 2

Substitution Theorem - 3

Applications of the Substitution Theorem - 1

Applications of the Substitution Theorem - 2

Applications of the Substitution Theorem - 3

Applications of the Substitution Theorem - 4

Reversal, Intersection with RL

Intersection with a RL - 1

Intersection with a RL - 2

Theorem 7.29

Inverse Homomorphism

Inverse homomorphism proof - 1

Inverse homomorphism proof - 2

Linear Conversion Algorithms

Complexity: Converting among CFGs & PDAs

Running Time of Conversion to CNF

Testing Emptiness of CFLs

Testing Membership in a CFL

CYK Algorithm - 2

Alt CYK Algo - 1

Alt CYK Algo - 2

Alt CYK Algo - 3

Alt CYK Algo - 4

Alt CYK Algo - 5

Alt CYK Algo - 6

Alt CYK Algo - 7

Alt CYK Algo - 8

Preview of Undecidable CFL Problems

Copyright and IP Notice

Author: Dr. J

E-mail: Juliano@ecst.csuChico.edu

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

Further information:
Computer Science @ California State University, Chico

StarOffice