| Introduction | p. 1 |
| Mathematical Background | p. 3 |
| Sets | p. 3 |
| Relations | p. 7 |
| Graphs | p. 11 |
| Proofs | p. 15 |
| Exercises | p. 18 |
| Languages | p. 25 |
| Formalization of languages | p. 25 |
| Expressions and grammars | p. 33 |
| Expressions | p. 33 |
| Grammars | p. 34 |
| Specification of a programming language | p. 39 |
| Translations | p. 48 |
| Exercises | p. 52 |
| Programming Projects | p. 57 |
| Automata | p. 59 |
| Conceptualization of automata | p. 59 |
| Transducers | p. 71 |
| Computability | p. 78 |
| Exercises | p. 82 |
| Programming Projects | p. 88 |
| Bibliographic notes | p. 90 |
| Regular Languages | p. 91 |
| Models for Regular Languages | p. 93 |
| Regular expressions | p. 93 |
| Finite automata | p. 99 |
| Basic definitions | p. 99 |
| Elimination of [varepsilon]-moves | p. 122 |
| Determinism | p. 145 |
| Simplification | p. 156 |
| Minimization | p. 171 |
| Finite Automata and regular expressions | p. 175 |
| From regular expressions to finite automata | p. 175 |
| Conversion of regular expressions to finite automata | p. 175 |
| Scanning | p. 196 |
| From finite automata to regular expressions | p. 209 |
| Equivalence of finite automata and regular expressions | p. 219 |
| Exercises | p. 220 |
| Programming projects | p. 227 |
| Properties of Regular Languages | p. 229 |
| Pumping lemma | p. 229 |
| Closure properties | p. 237 |
| Decidable problems | p. 250 |
| Exercises | p. 259 |
| Bibliographic notes | p. 265 |
| Context-Free Languages | p. 267 |
| Models for Context-Free Languages | p. 269 |
| Context-free grammars | p. 269 |
| Basic definitions | p. 269 |
| Ambiguity | p. 299 |
| Simplification | p. 305 |
| Elimination of useless symbols | p. 305 |
| Elimination of [varepsilon]-productions | p. 321 |
| Elimination of unit productions | p. 334 |
| Proper context-free grammars | p. 346 |
| Normal forms | p. 347 |
| Chomsky normal form | p. 348 |
| Greibach normal form | p. 357 |
| Pushdown automata | p. 381 |
| Basic definitions | p. 381 |
| Extension | p. 415 |
| Determinism | p. 432 |
| Pushdown automata and context-free grammars | p. 441 |
| From context-free grammars to pushdown automata | p. 442 |
| Conversion of context-free grammars to pushdown automata | p. 442 |
| Parsing | p. 477 |
| From pushdown automata to context-free grammars | p. 486 |
| Equivalence of pushdown automata and context-free grammars | p. 494 |
| Exercises | p. 495 |
| Programming projects | p. 508 |
| Properties of Context-Free Languages | p. 511 |
| Pumping lemma | p. 511 |
| Closure properties | p. 528 |
| Decidable problems | p. 551 |
| Exercises | p. 558 |
| Special Types of Context-Free Languages and Their Models | p. 565 |
| Deterministic context-free languages | p. 565 |
| Linear and regular grammars | p. 574 |
| Exercises | p. 599 |
| Bibliographic notes | p. 605 |
| Beyond Context-Free Languages | p. 607 |
| Generalized Models | p. 609 |
| Turing machines | p. 609 |
| Basic definitions | p. 609 |
| Determinism | p. 631 |
| Simplification | p. 643 |
| Extension | p. 652 |
| Universality | p. 674 |
| Turing machines that always halt | p. 693 |
| Linear-bounded automata | p. 695 |
| Two-pushdown automata | p. 696 |
| Basic definitions | p. 696 |
| Determinism | p. 704 |
| Equivalence of two-pushdown automata and Turing machine | p. 705 |
| Unrestricted grammars | p. 707 |
| Basic definition | p. 708 |
| Equivalence of unrestricted grammars and Turing machines | p. 713 |
| Normal forms | p. 722 |
| Context-sensitive grammars | p. 729 |
| Basic definition | p. 730 |
| Context-sensitive grammars and linear-bounded automata | p. 732 |
| Context-sensitive languages and recursive languages | p. 735 |
| Normal forms of context-sensitive grammars | p. 740 |
| Hierarchy of language families | p. 742 |
| Exercises | p. 743 |
| Programming projects | p. 753 |
| Bibliographic notes | p. 755 |
| Translations | p. 757 |
| Finite and Pushdown Transducers | p. 758 |
| Finite transducers | p. 758 |
| Translation grammars and pushdown transducers | p. 770 |
| Translation grammars | p. 770 |
| Pushdown transducers | p. 776 |
| Compilers | p. 787 |
| Compiler structure | p. 788 |
| Scanner | p. 789 |
| Parser, semantic analyzer, and code generator | p. 806 |
| Optimizer | p. 818 |
| Execution | p. 820 |
| Exercises | p. 822 |
| Programming projects | p. 832 |
| Turing Transducers | p. 833 |
| Basic definitions | p. 833 |
| Computability | p. 845 |
| Computers | p. 845 |
| Computable functions | p. 851 |
| Uncomputable functions | p. 853 |
| Decidability | p. 856 |
| Decision makers | p. 856 |
| Decidable problems | p. 860 |
| Computational complexity | p. 861 |
| Time complexity | p. 862 |
| Space complexity | p. 866 |
| Undecidable problems | p. 867 |
| Undecidability: a general approach | p. 872 |
| Exercises | p. 874 |
| Programming projects | p. 884 |
| Bibliographic notes | p. 886 |
| Bibliography | p. 889 |
| Indices | p. 901 |
| Index to Special Symbols | p. 903 |
| Index to Decision Problems | p. 905 |
| Index to Algorithms | p. 907 |
| Subject Index | p. 911 |
| Table of Contents provided by Syndetics. All Rights Reserved. |
