Название: Foundations of Computing: An Accessible Introduction to Formal Languages
Автор: Charles D. Allison
Издательство: Leanpub
Год: 2021-07-01
Страниц: 286
Язык: английский
Формат: pdf (true), epub
Размер: 64.7 MB

An accessible, practical approach to formal languages with an introduction to computability.

A textbook for upper-division Computer Science majors covering formal languages and automata with an introduction to computability. Intended to give CS majors a solid foundation in the Theory of Computation without being overly formal mathematically, while retaining the rigor of the material.

I wrote this book to make the fundamentals of the theory of computation more accessible to the current generation of undergraduate computer science students. Over the course of twenty 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 computation 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, first-order 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 symbol 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/accepting states and an empty stack simultaneously 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; it is often referred to as “executable pseudocode.” It is in widespread use in many computing domains and is universally available. An effective innovation is the use of Python program to teach reductions of one unsolvable problem to another in a compact chapter on computability.