Theory of Computing

Table of contents

Title

CFGs

Definition of CFGs

CFG Example - 1

CFG Example - 2

Derivations using a Grammar

Left-/Right-most Derivations

Language of a Grammar

Sentential Forms

Parse Trees

Parse Tree Example - 1

Parse Tree Example - 2

Yield of a Parse Tree

Yield Example

Inference, Derivations, and Parse Trees

From Inferences to Trees

Proof of Thm 5.12 - 1

Proof of Thm 5.12 - 2

Proof of Thm 5.12 - 3

From Trees to Derivations

Proof of Thm 5.14 - 1

Proof of Thm 5.14 - 2

Proof of Thm 5.14 - 3

Proof of Thm 5.14 - 4

Proof of Thm 5.14 - 5

Proof of Thm 5.14 - 6

Theorem 5.16

From Derivations to Recursive Infereces

Proof of Thm 5.18 - 1

Proof of Thm 5.18 - 2

Proof of Thm 5.18 - 2

CFG Applications

Ambiguous Grammars

Ambiguity Example

Remove Ambiguity

Ex Ambiguity Removal - 1

Ex Ambiguity Removal - 2

Ex Ambiguity Removal - 3

Ex Ambiguity Removal - 4

Example

Expressing Ambiguity

Inherent Ambiguity

Inherent Ambiguity - 2

Inherent Ambiguity - Ex 1

Inherent Ambiguity - Ex 2

Inherent Ambiguity - Ex 2

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