Book presentation: Models of Computation based on Automata: Formal Languages and Communicating Processes
Jos Baeten
First-year students in computer science and related fields usually follow a course on Automata Theory and Formal Languages. This course gives students the foundations of computer science, and tells them what a computer can and cannot do. The course is usually based on the computer model called the Turing Machine, which adequately describes a computer as they were in the seventies: a stand-alone machine executing batch processes. However, the Turing machine is blind, deaf and dumb, very different from computers as we know them today. I would not let a Turing machine drive my car. This book integrates automata theory with process theory, and treats, alongside the classical results on correspondences between types of automata and grammars, their generalisations to a setting that facilitates communication and interaction, and moreover contains some new results. In just 200 pages with plenty of exercises, it can serve as a replacement of the classical course for first-year students.