Context-Free Grammars and Languages
Overview
The next set of lectures will concern a provably more powerful way to represent languages, namely, the use of context-free grammars. Following an introduction of these and a suggestion of a way to design context-free grammars for various languages, the concept of ambiguity (and the advantage of avoiding it) will be introduced. A special kind of context-free grammar, “Chomsky normal form”, will be presented and applied to develop an algorithm to decide whether a given string belongs to the language of a given context-free grammar. Finally, a method to prove that a given language is not context-free will be given.
Lecture #12: Introduction to Context-Free Grammars
Required Reading
- Lecture Notes: [ PDF ] [ Video ]
- Supplement: Proof that a Context-Free Grammar has a Given Language [ PDF ]
Lecture Presentation
Lecture #13: Design and Verification of Context-Free Grammars (Part One)
Required Reading
- Lecture Notes: [ PDF ] [ Video ]
- Supplement: Regular Languages are Context-Free — Completion of the Proofs [ PDF ]
Lecture Presentation
Tutorial Exercise #9: Design and Verification of Context-Free Grammars (Part One)
Lecture #14: Design and Verification of Context-Free Grammars (Part Two)
Required Reading
- Lecture Notes: [ PDF ] [ Video ]
- Supplement: On the Existence of Parse Trees and Proofs of Useful Claims [ PDF ]
Lecture Presentation
Tutorial Exercise #10: Design and Verification of Context-Free Grammars (Part Two)
Lecture #15: Ambiguity in Context-Free Grammars
Required Reading
Lecture Presentation
Tutorial Exercise #11: Ambiguity in Context-Free Grammars
Lecture #16: Chomsky Normal Form
Required Reading
Lecture Presentation
Tutorial Exercise #12: Chomsky Normal Form
Lecture #17: An Algorithm for Parsing
Required Reading
- Lecture Notes: [ PDF ] [ Video ]
- Supplement: A Faster Algorithm for Parsing (PDF)
