Key Topics Covered in the
Course
You should make sure that you have a firm understanding of the
following key concepts covered in the course.
- Regular Languages: (non)deterministic finite automata,
conversion from nondeterministic to deterministic automata, regular
expressions, equivalence between finite automata and regular
expressions, closure properties of regular languages, the Pumping
Lemma for regular languages, applications of the pumping lemma.
- Context-free Languages: context-free languages,
context-free grammars, derivations, parse trees, Chomsky normal form,
The Pumping Lemma for context-free grammars, applications of the
pumping lemma.
- Operational Semantics for While: configurations, transition systems,
modelling of program computations as transition systems, transition
systems defined via transition rules, derivation trees, states,
natural semantics, structural operational semantics.
- Operational Semantics for Extensions of While: semantic
equivalence, description of abortion, nondeterminism and
parallelism.
- Operational Semantics for Procedures: scope rules
(static/dynamic scope for variables and procedures), procedure
environments, environment-store model.
- Partial Correctness Assertions: Hoare triples of the form
P {S} Q and their intended meaning, proof rules for the constructs of
While, loop invariants, use of the rules to establish the
validity of partial correctness assertions.
Reading Material
- Chapter 1, and Sections 2.1, 2.3 of Introduction to
the Theory of Computation by Michael Sipser.
- Chapters 1, 2 (excluding the proofs of Theorems 2.9 and 2.26)
and pages 175-182 of Hanne
Riis Nielson, Flemming
Nielson: Semantics with Applications: A Formal
Introduction. Wiley Professional Computing, (240 pages, ISBN 0
471 92980 8), Wiley, 1992.
- Pages 219-227 of "Abstraction and Specification in Program
Development" by Barbara Liskov and John Guttag, MIT Press, 1986.
List of Exam Questions
1. Finite Automata: Deterministic, nondeterministic finite automata and their
equivalence.
2. Regular expressions and their connection with finite automata.
3. The Pumping Lemma for regular languages and its applications.
4. Context-free grammars and closure properties of context-free
languages.
5. The Pumping Lemma for context-free languages and its applications.
6. Natural and structural operational semantics for While.
7. Operational semantics for extensions of While.
8. Natural operational semantics for procedures with different scope
rules.
9. Partial correctness assertions.
Note! Slides with the rules for the natural and structural
operational semantics for the language While and its extensions
will be available for those of you who would like to use them at the
exam. Ditto for the rules of the formal system for partial correctness
assertions.