An Introduction to Formal Languages and Automata

Citation

Linz, P., & Rodger, S. H. (2023). An Introduction to Formal Languages and Automata (7th ed.). Jones & Bartlett Learning.

Chapter Summary

The seventh edition has seventeen chapters in two parts. Part I, "Theory", consists of the fourteen chapters of the sixth edition with new exercises; Part II, "Applications", is new and applies that theory to parsing in compilers. Two appendixes, solutions and hints for selected exercises, and references for further reading follow, for about 570 pages in all. Sections marked with an asterisk can be omitted without loss to later material. Every chapter now ends with a set of simple "Introductory Exercises" in addition to the established exercises.

Chapter 1: Introduction to the Theory of Computation

Reviews the mathematical preliminaries (sets, functions and relations, graphs and trees, proof techniques), then introduces the three basic concepts of the book: languages, grammars and automata. An optional section sketches applications.

Chapter 2: Finite Automata

Defines deterministic finite accepters with transition graphs and uses them to define regular languages, then introduces nondeterministic accepters, explains why nondeterminism is useful, and proves the two kinds equivalent. An optional section reduces the number of states.

Chapter 3: Regular Languages and Regular Grammars

Introduces regular expressions and proves that they describe exactly the regular languages, including their use for describing simple patterns. Right- and left-linear grammars are shown to generate the same family.

Chapter 4: Properties of Regular Languages

Covers closure under set and other operations, elementary decision questions, and ways of showing that a language is not regular, using the pigeonhole principle and a pumping lemma.

Chapter 5: Context-Free Languages

Introduces context-free grammars, leftmost and rightmost derivations and derivation trees, then parsing, membership and ambiguity, and closes with the role of context-free grammars in programming languages.

Chapter 6: Simplification of Context-Free Grammars and Normal Forms

Shows how to remove useless, λ- and unit-productions, and presents Chomsky and Greibach normal forms. An optional section gives a membership algorithm for context-free grammars.

Chapter 7: Pushdown Automata

Defines nondeterministic pushdown automata and proves their equivalence with context-free grammars in both directions, then treats deterministic pushdown automata and deterministic context-free languages, with an optional section on their grammars.

Chapter 8: Properties of Context-Free Languages

Gives pumping lemmas for context-free and for linear languages, closure properties, and some decidable properties of context-free languages.

Chapter 9: Turing Machines

Defines the standard Turing machine as a language accepter and as a transducer, shows how machines can be combined for complicated tasks, and states Turing's thesis.

Chapter 10: Other Models of Turing Machines

Examines variations (stay-option, semi-infinite tape, off-line machines), machines with more complex storage (multitape and multidimensional), nondeterministic machines, the universal Turing machine and linear bounded automata, establishing which variations add no power.

Chapter 11: A Hierarchy of Formal Languages and Automata

Distinguishes recursive and recursively enumerable languages and exhibits languages outside each class, then introduces unrestricted and context-sensitive grammars and assembles the Chomsky hierarchy.

Chapter 12: Limits of Algorithmic Computation

Treats computability and decidability, the halting problem, reduction of one undecidable problem to another, undecidable problems for recursively enumerable and context-free languages, and the Post correspondence problem, ending with a short look at efficiency.

Chapter 13: Other Models of Computation

Presents alternative models: primitive recursive and μ-recursive functions with Ackermann's function, Post systems, and rewriting systems such as matrix grammars, Markov algorithms and L-systems.

Chapter 14: An Overview of Computational Complexity

Relates Turing machine models to complexity, introduces language families and complexity classes, P and NP with examples of NP problems, polynomial-time reduction and NP-completeness, ending with the open question of whether P equals NP.

Chapters 15–17: Compilers and Parsing; LL Parsing; LR Parsing

Part II begins with what compilers do, top-down versus bottom-up parsing, and the FIRST and FOLLOW functions. Chapter 16 converts a context-free grammar to a nondeterministic pushdown automaton for LL parsing and builds the LL(1) parse table and parsing algorithm, with a section on LL(k). Chapter 17 does the same for LR parsing: items and closure, a DFA modelling the parsing stack, the LR(1) parse table and algorithm, λ-productions and parsing conflicts.

Appendixes

Appendix A covers finite-state transducers (Mealy and Moore machines, their equivalence, minimization and limitations). Appendix B introduces JFLAP, a free interactive tool for building and testing automata and grammars.

Key Concepts

Chapters 1–4: Foundations and Regular Languages

• Language, grammar, automaton: the three basic notions of the book, introduced together in Chapter 1.
• Nondeterminism: allowing several possible moves; for finite accepters it adds convenience but no power.
• Regular expression: a notation that describes exactly the languages accepted by finite automata.
• Pumping lemma: a property of all regular languages used to prove that a given language is not regular.

Chapters 5–8: Context-Free Languages

• Derivation tree and ambiguity: the structure of a derivation, and grammars that allow more than one tree for a string.
• Chomsky and Greibach normal forms: restricted grammar forms that every context-free language can be given.
• Pushdown automaton: a finite automaton with a stack, equivalent in its nondeterministic form to context-free grammars.

Chapters 9–13: Turing Machines and Computability

• Turing's thesis: the claim that any mechanical computation can be carried out by a Turing machine.
• Universal Turing machine: a machine that simulates any other from its description.
• Chomsky hierarchy: the nested families of regular, context-free, context-sensitive and recursively enumerable languages.
• Halting problem and reduction: the basic undecidable problem and the method used to show others undecidable.

Chapter 14: Complexity

• P and NP: problems solvable in deterministic and in nondeterministic polynomial time.
• NP-completeness: the hardest problems in NP under polynomial-time reduction.

Chapters 15–17: Parsing

• FIRST and FOLLOW: functions on grammar symbols used to build parse tables.
• LL(1) and LR(1) parsing: top-down and bottom-up table-driven parsing with one symbol of lookahead, derived from pushdown automata.

Critical Analysis

Strengths

• Intuition and examples first. The preface says the text stresses intuitive motivation and illustration through examples, prefers arguments that are easy to grasp over concise but difficult ones, and introduces central ideas with a motivating example.
• Learning through problems. Exercises at the end of each section range from simple continuations of the text to very difficult problems, and the seventh edition adds chapter-end Introductory Exercises as a bridge to the harder ones. Solutions and hints for selected exercises are included.
• A direct answer to "why does this matter?" Part II applies pushdown automata and grammars to LL and LR parsing, in response, the authors say, to students' questions about the practical use of the theory.
• Tool support. Appendix B introduces JFLAP, a free interactive tool that the preface strongly recommends for understanding the concepts and for saving time when constructing solutions to exercises.

Limitations

• Brief proofs. The preface acknowledges that many proofs give only the motivation and leave out routine details; readers who want complete formal proofs will need a more rigorous text or will have to fill in the steps themselves.
• Complexity only in overview. Computational complexity occupies one chapter that ends at NP-completeness; space complexity and later topics are not treated.
• More than a semester holds. The preface says most of Part I can be covered in one semester only with some choice of emphasis, and fitting in Part II means treating later sections of Part I lightly.

Where It Fits in the Course

Within the theory-of-computation course this is a gentle first textbook that covers the standard sequence from finite automata to NP-completeness. MacCormick's What Can Be Computed? is the other introductory option: it approaches computability and complexity through Python programs, gives finite automata a single chapter and has no chapters on grammars or pushdown automata. Linz and Rodger is the better fit when the course spends much of its time on formal languages, and the two complement each other well.

Kozen's Automata and Computability (short lectures with full proofs), Hopcroft, Motwani and Ullman's Introduction to Automata Theory, Languages, and Computation and Sipser's Introduction to the Theory of Computation cover similar ground with more formal proofs; students who find Linz's proof sketches too brief can read the corresponding sections there. Arora and Barak's Computational Complexity is a graduate text that takes complexity far beyond the overview in Chapter 14.

How to Use This Book

The preface addresses second- and third-year computer science and computer engineering students. It names as prerequisites a high-level programming language, the fundamentals of data structures and algorithms, and an essential course in discrete mathematics covering sets, functions, relations, logic and mathematical reasoning.

• Core (Part I): Chapters 1–12 in order; the preface warns that little can be skipped without later difficulty, apart from the starred sections (for example 1.3, 2.4, 6.3, 7.4).
• Lighter treatment: according to the preface, many sections in the latter part of Part I can be treated lightly or skipped without loss of continuity, freeing about a week for Part II; Chapter 13 on other models of computation is a natural candidate.
• Complexity: Chapter 14 gives a first view of P, NP and NP-completeness.
• Applications (Part II): Chapters 15–17 suit students heading for a compilers course, or as guided reading if class time runs out.

Work the Introductory Exercises first to check understanding of each definition, then move to the main exercises. Build every automaton and grammar from the examples in JFLAP and test it on strings before writing proofs. When the book sketches a proof, write out the missing details yourself; this is the practice the preface recommends.