Specifying Software (Q4328792)

This volume provides a hands-on introduction to techniques for specifying the behaviour of software components. Featured topics include techniques for using programmers-friendly assertional notations to specify, develop, and verify small but nontrivial algorithms and data representations and for using state diagrams, grammars, and regular expressions to specify and develop recognizers for formal languages. 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 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 indented to be 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. The contents max 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, specification and systematic development of recognizers for formal languages using regular expressions, grammars, and automata. So, the reader finds four parts: A: Algorithms, B: Data Representations, C: Language Recognizers, D: Unimplementable Specifications. Part A comprises specifying algorithms, basic techniques and additional techniques to verifying of algorithms. Part B comprises a case study and additional examples of data representation. Part C comprises notes on basic concepts, state diagrams, regular languages, context free languages, and parsing. Part D comprises a taste of computability theory. Appendices contain two parts: A: Programming Language Reference, B: Hints for Selected Exercises. Using this book will help readers improve their programming skills and develop a solid foundation for subsequent courses in advanced algorithms and data structures, software design, formal methods, and compilers.