Following a general discussion of formal languages, their descriptions, and borderline cases of recognizability, the chapter covers regular languages—which find their most important application in the lexical definition of programming languages—as well as context-free languages, which are used to define the syntax of programming languages. From a theoretical perspective, the clear correspondence between language description and language recognition is satisfying—finite automata correspond to regular languages, and pushdown automata correspond to context-free languages. Further levels of the Chomsky hierarchy are only briefly covered, as they are of lesser practical importance. Instead, a separate chapter on compiler design highlights additional techniques for deriving a parser—that is, the complete "front end" of a compiler—from a language description. The concept of an "algorithm" is explained using various machine models, and Church’s thesis—that every reasonable definition of "computability" leads to the same class of functions—is also confirmed. The limits of what is algorithmically feasible are clearly delineated using the halting problem and Rice’s theorem. The concluding chapter on complexity theory explores, among solvable problems, the boundary between those that can be solved with reasonable (polynomial) effort and those whose solution is not significantly more efficient than systematically trying out candidate solutions. This chapter leads the reader to the most famous unsolved problem in theoretical computer science: P = NP?The first volume of Computer Science explains the fundamental concepts: programming, algorithms, and data structures. The second volume is devoted to technical topics—in particular, computer architecture, operating systems, computer networks, and specifically the Internet.The book is intended for all beginners who wish to seriously engage with computer science, whether for self-study or to accompany lectures. The subsequent...