Foundations of Computing
An Introduction to Formal Languages
Charles D. Allison, Utah Valley University
Copyright © Fresh Sources, Inc., 2016–2018
All Rights Reserved
Cover art by Doug Hamilton, “Feather Moon” (doughamiltonart.com)
I am personally convinced that any science progresses as much by the writing of better textbooks as by the generation of new knowledge, because good textbooks are what allows the next generation to learn the older stuff quickly and well so we can move on to interesting new things instead of having to painstakingly decipher the discoveries of our forebears.
– Jaap Weel
I wrote this book to make the fundamentals of theory of computation more accessible to the current generation of undergraduate computer science students. Over the course of sixteen years of teaching this subject at Utah Valley University (UVU) in Orem, Utah, I have noticed that computer science undergraduates are not as mathematically sophisticated as in the early days of computer science education—when CS students mostly came from mathematics and the sciences—yet the demand for CS graduates has increased dramatically, with enrollments at UVU and elsewhere following suit. Furthermore, the areas where computing applies to daily life have broadened to the point that society can’t seem to do without the convenience that computerized devices afford. CS graduates can make a noticeable contribution to the world of computing work without as much mastery of formal mathematics as was required in times past.
Yet it is crucial that a practicing software engineer understand the nature and limits of computation. As the artist must have familiarity with media and the scientist with elements and equipment, the computing practitioner must know what software can and can’t do. In this book, I attempt to illuminate the fundamentals of computing for as large an audience as possible. The key results of the theory of computing are covered with numerous examples and sometimes even with working Python programs, while at the same time achieving a measure of rigor with only a minimum of mathematical formalism. Formal proofs appear infrequently, but constructive arguments abound. I use recursive definitions, but use mathematical induction only twice. While mathematical notation appears as needed, I use visual representations profusely to illustrate concepts.
I assume that readers have basic programming knowledge as one would encounter in typical CS1 and CS2 courses, and familiarity with introductory discrete mathematics, including sets, relations, functions, modular arithmetic, the notion of a logarithm, basic propositional and predicate logic, and the structure of simple, directed graphs.
The emphasis is on the structure, properties, and application of formal languages, along with an introductory exposure to computability. Complexity theory is not covered, as it is the topic of a separate undergraduate course on algorithms at UVU. Parsing is only touched on since that topic is covered exhaustively in our compiler course required of CS majors.
I use a uniform approach to transition graphs for the different types of finite-state machines so students feel at home when new features are added. For example, for pushdown automata, I use the same graph notation as for finite automata, only adding stack operations, and only pop one character at a time. In addition, when stack start symbols are used, I explicitly push them in the graph, minimizing changes to what students are already accustomed to with finite automata. Furthermore, I require both final states and an empty stack for PDA acceptance. This avoids needless discussion of how to convert acceptance by empty stack to and from acceptance by accepting state only, and makes it easier to show that deterministic pushdown automata are closed under complement, as well as making converting PDAs to context-free grammars less exceptional.
Several programming examples appear, and a small number of modest programming projects appear in the exercises. I use Python 3. Python is among the most readable of programming languages, so much so that it is often referred to as “executable pseudocode.” It is in widespread use in many computing domains and is universally available.
I wish to acknowledge the helpful comments of reviewers Matt Bailey, Tyler Barney, Eric Belliston, Kevin Black, Curtis Boland, Jordan Carter, Josh Chevrier, Thomas Christiansen, Cameron Clay, Brennen Davis, Daniel Dayley, Michael Elliott, Ryan Ferguson, Phillip Goettman, Quinn Heap, Gregory Hodgson, Chad Holt, Joel Johnson, Josh Jones, Ethan Kikuchi, Jared Leishman, Ryan Lever, Caleb MacDonald, Nate Madsen, Natalie Madsen, Wesley Mangrum, Juan Medrano, Michael Mickelson, LuAnne Mitchell, Kelly Nicholes, Eric Nielson, Kris Olson, Timothy Marc Owens, Kailee Parkinson, Cody Powell, Jake Prestwich, Zachary Price, Andrew Ripley, Devin Rowley, Drew Royster, Gail Sanders, Vani Satyanarayan, Blaine Sorenson, Benjamin Thornhill, and Jeremy Warren, all UVU alumni. Doug Hamilton also provided corrections in addition to his beautiful art work on the cover. A special thanks to Dr. Keith B. Olson, my long-time colleague and fellow mathematician, for his edits, insights, and encouragement. I also drew inspiration from Dr. Peter J. Downey, who taught me this subject decades ago at the University of Arizona.
I hope CS students will find this book helpful in understanding what computers can and cannot do, in gaining insights into crafting programs for problems that involve various states or text processing, and in comprehending more fully the nature of computation.
Chuck Allison, 2018
*** All images, unless otherwise indicated, are property of the author. ***