The course is an introduction into the very large domain of software specifications. We cover the basics that will be built upon in several advanced courses on topics including theoretical computer science, compiler design, software engineering, and formal methods. The goal of the course is to offer to all CS students a basic understanding of many of the “hard” topics in computer science.
The course is therefore divided into two main parts: The first part offers an introduction into specification and systematic development of recognizers for formal languages using regular expressions, grammars, and automata, while the second part addresses specification, verification, and development of simple algorithms using pre- and post-conditions and loop invariants. Some further incursions into program verification will also be contemplated.
The following is a however tentative schedule:
Introduction to formal languages | 1 week |
Regular languages and state transition diagrams | 2 weeks |
Context-free languages | 2 weeks |
Introduction to specifications | 1 week |
Reasoning about specifications | 2 weeks |
Examples of algorithms | 1 week |
Formal methods | 2 weeks |
Introduction to computability | 1 week |