Preface

Summary

This book was written to support a short course in the second or third year of an undergraduate computer science, software engineering, or software design program. The prerequisites are fairly modest: some programming experience (ideally in C or C++ or a related language such as JAVA) and some exposure to the most basic concepts of discrete mathematics (sets, functions, binary relations, sequences) and to the language of elementary logic (connectives and quantifiers). It is intended to be only an introduction to software specifications, not a systematic survey of requirements engineering, formal methods, compilers, or computation theory suitable for a senior or graduate-level course. A course based on this book would provide a good foundation for such courses but should not replace them.

The contents may be summarized briefly as follows:

• specification, verification, and development of simple algorithms using pre- and post-conditions and loop invariants;

• specification, verification, and development of simple data representations using abstract models and representation invariants; and

• specification and systematic development of recognizers for formal languages using regular expressions, grammars, and automata.

These techniques have been well studied and are sound and useful. They may be presented to and immediately used by undergraduate students on simple but nontrivial examples. They may be taught without requiring upper-level prerequisites or major investments of time to teach complex notations or computer-based tools. But such material is not often presented at this level, nor in this combination.