I am Dr. Adam Brooks Webber, an associate professor at Monmouth College. Here are the highlights, in a short question-and-answer style, of my new book, Formal Language: A Practical Introduction. (ISBN 1-590281-97-7)
The book is a undergraduate college-level introduction to formal languages, automata, computability, and complexity —topics at the foundations of computer science.
This book is written to be understood by all undergraduate students, regardless of their level of mathematical maturity.
Ask yourself this question: when you teach a course in the theory of computation, how many of your students really understand inductive proofs? How many can create novel inductive proofs? How many can still do it a month after the final exam? Be honest! If you find that a high percentage can successfully master inductive proof technique, congratulations—and this book is not for you. If you find, as I and many of my colleagues do, that it is a disappointingly low percentage, read on.
There are a number of beautiful textbooks on the theory of computation, but they assume a level of mathematical maturity and interest that only a few students actually have. Most of my students are bright people whose primary interest in computing is practical. They like programming and have some aptitude for it. They have little interest in mathematical abstractions. They hope to find jobs in the computing industry. They think (sometimes incorrectly) that they are not going to do graduate work on the academic side of computer science.
In general, my students do not thrive on a diet of unmotivated abstractions. The book tries to lead them gently into the beautiful abstractions at the foundations of computer science, using concrete examples and exercises. For example, chapters on finite automata are include applications and implementation techniques; chapters on stack-based automata include a discussion of applications to compiler construction; chapters on computability used simple Java-like code examples. Included among the exercises are a number of Java programming problems, which can be used both to hold student interest and to enhance their understanding.
There's no doubt that the theory of formal languages and automata is an ideal place to introduce induction and other proof techniques, for students who need to learn them. The book includes one chapter, and a number of exercises, covering inductive proofs. However, the material is not central to the book, and the instructor can use as much or as little of it as desired.
The book includes clear proofs for almost all the theorems, but stops short of presenting detailed inductions. The exercises rarely require students to generate novel proofs. My feeling is that too much stress on proof technique turns many students off. The concepts of formal languages and automata are among the most beautiful and enduring in all of computer science, and have many practical applications as well. The book tries to make these treasures accessible to all students, not just those with a knack for the mathematically rigorous proof.
The course for which I developed the book is called Introduction to the Theory of Computation. It is a required course for undergraduate computer science majors at the University of Wisconsin - Milwaukee. The course does not rely on any mathematical prerequisites. It does require some ability to read simple code examples: a Java-like syntax is used, but the ability to read any C-family language will suffice. The book can be used for any undergraduate course in formal languages, automata, and computability.
In many CS and CE departments, as at UWM, this is a required course. At other institutions the course has gradually fallen into disuse: it has sometimes become an elective, rarely if ever offered. The reason for this decline, I believe, is the mismatch between the students and the treatment of the subject. Instructors do not enjoy the drudgery of having to frog-march undergraduates through a difficult textbook that they barely understand and quickly forget; students enjoy the experience even less. I hope that Formal Language: A Practical Introduction will help to rekindle the excitement of teaching and studying this subject.
This is the table of contents.
CHAPTER 1: FUNDAMENTALS
1.1 Alphabets
1.2 Strings
1.3 Languages
CHAPTER 2: FINITE AUTOMATA
2.1 Man Wolf Goat Cabbage
2.2 Not Getting Stuck
2.3 Deterministic Finite Automata
2.4 The 5-Tuple
2.5 The Language Accepted by a DFA
Exercises
CHAPTER 3: CLOSURE PROPERTIES FOR REGULAR LANGUAGES
3.1 Closed Under Complement
3.2 Closed Under Intersection
3.3 Closed Under Union
3.4 DFA Proofs Using Induction
3.5 A Mystery DFA
Exercises
CHAPTER 4: DFA APPLICATIONS
4.1 DFA Applications
4.2 A DFA-Based Text Filter in Java
4.3 Table-Driven Alternatives
Exercises
CHAPTER 5: NONDETERMINISTIC FINITE AUTOMATA
5.1 Relaxing a Requirement
5.2 Spontaneous Transitions
5.3 Nondeterminism
5.4 The 5-Tuple for an NFA
5.5 The Language Accepted by an NFA
Exercises
CHAPTER 6: NFA APPLICATIONS
6.1 NFA Implemented With Backtracking Search
6.2 NFA Implemented With Bit-Mapped Parallel Search
6.3 The Subset Construction
6.4 NFAs Are Exactly As Powerful As DFAs
6.5 DFA Or NFA?
Further Reading
Exercises
CHAPTER 7: REGULAR EXPRESSIONS
7.1 Regular Expressions, Formally Defined
7.2 Regular Expression Examples
7.3 For Every Regular Expression, a Regular Language
7.4 Regular Expressions and Structural Induction
7.5 For Every Regular Language, a Regular Expression
Exercises
CHAPTER 8: REGULAR EXPRESSION APPLICATIONS
8.1 The egrep Tool
8.2 Non-Regular Regexps
8.3 Implementing Regexps
8.4 Regular Expressions in Java
8.5 The lex Tool
Further Reading
Exercises
CHAPTER 9: ADVANCED TOPICS IN REGULAR LANGUAGES
9.1 DFA Minimization
9.2 Two-Way Finite Automata
9.3 Finite-State Transducers
9.4 Advanced Regular Expressions
Further Reading
Exercises
CHAPTER 10: GRAMMARS
10.1 A Grammar Example for English
10.2 The 4-Tuple
10.3 The Language Generated by a Grammar
10.4 Every Regular Language Has a Grammar
10.5 Right-Linear Grammars
10.6 Every Right-Linear Grammar Generates a Regular Language
Exercises
CHAPTER 11: NON-REGULAR LANGUAGES
11.1 The Language {anbn}
11.2 The Languages {xxR}
11.3 Pumping
11.4 Pumping-Lemma Proofs
11.5 Strategies
11.6 Pumping And Finite Languages
Exercises
CHAPTER 12: CONTEXT-FREE LANGUAGES
12.1 Context-Free Grammars and Languages
12.2 Writing CFGs
12.3 CFG Applications: BNF
12.4 Parse Trees
12.5 Ambiguity
12.6 EBNF
Exercises
CHAPTER 13: STACK MACHINES
13.1 Stack Machine Basics
13.2 A Stack Machine For {anbn}
13.3 A Stack Machine For {xxR}
13.4 Stack Machines, Formally Defined
13.5 Example: Equal Counts
13.6 Example: A Regular Language
13.7 A Stack Machine For Every CFG
13.8 A CFG For Every Stack Machine
Exercises
CHAPTER 14: THE CONTEXT-FREE FRONTIER
14.1 Pumping Parse Trees
14.2 The Language {anbncn}
14.3 Closure Properties For CFLs
14.4 Non-Closure Properties
14.5 A Pumping Lemma
14.6 Pumping-Lemma Proofs
14.7 The Languages {xx}
Exercises
CHAPTER 15: STACK MACHINE APPLICATIONS
15.1 Top-Down Parsing
15.2 Recursive Descent Parsing
15.3 Bottom-Up Parsing
15.4 PDAs, DPDAs, and DCFLs
Further Reading
Exercises
CHAPTER 16: TURING MACHINES
16.1 Turing Machine Basics
16.2 Simple TMs
16.3 A TM For {anbncn}
16.4 The 7-Tuple
16.5 The Languages Defined By A TM
16.6 To Halt Or Not To Halt
16.7 A TM For {xcx | x ∈ {a,b}* }
16.8 Three Tapes
16.9 Simulating DFAs
16.10 Simulating Other Automata
Further Reading
Exercises
CHAPTER 17: COMPUTABILITY
17.1 Turing-Computable Functions
17.2 TM Composition
17.3 TM Arithmetic
17.4 TM Random Access
17.5 Functions And Languages
17.6 The Church-Turing Thesis
17.7 TM and Java Are Interconvertible
17.8 Infinite Models, Finite Machines
Exercises
CHAPTER 18: UNCOMPUTABILITY
18.1 Decision and Recognition Methods
18.2 The Language Lu
18.3 The Halting Problems
18.4 Reductions Proving a Language Is Recursive
18.5 Reductions Proving a Language Is Not Recursive
18.6 Rice's Theorem
18.7 Enumerators
18.8 Recursively Enumerable Languages
18.9 Languages That Are Not RE
18.10 Language Classifications Revisited
18.11 Grammars And Computability
18.12 Oracles
18.13 Mathematical Uncomputabilities
Exercises
CHAPTER 19: COST MODELS
19.1 Asymptotic Notation
19.2 Properties of Asymptotics
19.3 Common Asymptotic Functions
19.4 A TM Cost Model
19.5 A Java Cost Model
Exercises
CHAPTER 20: DETERMINISTIC COMPLEXITY CLASSES
20.1 Time Complexity Classes
20.2 Polynomial Time
20.3 Exponential Time
20.4 Space Complexity Classes
20.5 Higher Complexity Classes
Further Reading
Exercises
CHAPTER 21: NONDETERMINISTIC COMPLEXITY CLASSES
21.1 Verification Methods
21.2 NP, NP-Hard, And NP-Complete
21.3 A Tour of Six Decision Problems
21.4 The Wider World of NP-Complete Problems
21.5 Nondeterministic Turing Machines
21.6 The Million Dollar Question
Further Reading
Exercises
APPENDIX A: NFA TO REGULAR EXPRESSION
A.1 The Internal Languages of an NFA
A.2 The d2r Function
A.3 Proof of Lemma 7.5
APPENDIX B: A TIME HIERARCHY THEOREM
B.1 Another Asymptotic Notation: Little o
B.2 Time-Constructible Functions
B.3 Cost Model For run and runWithTimeLimit
B.4 Time Hierarchy Theorem
B.5 Application
APPENDIX C: SOME NP-HARDNESS PROOFS
C.1 Cook's Theorem: SAT is NP-hard
C.2 CNFSAT is NP-hard
C.3 Vertex Cover is NP-hard
C.4 Hamiltonian Circuit is NP-hard
The web site for the book will provide a full set of PowerPoint lecture notes for each chapter. All the larger code examples from the text and exercises are there too. Sample solutions to the exercises are available through the publisher.
I can only say for sure that it works for me. The semester that I used the new book, the students in the College of Engineering and Applied Science at the University of Wisconsin - Milwaukee voted me the best teacher of the semester. But my feeling is that there is no one best approach, no single solution that will fit all teachers and all students. As you know, if there is a magic ingredient in any successful course, it is the teacher's enthusiasm. Of course, that may be why the book works well for me: I wrote it, so naturally I am enthusiastic about it, and that enthusiasm does more for students than any book ever could. But if your students are at all like mine, I think there is a good chance this book will suit them, and you.
The book will be available this summer, with ISBN 1-590281-97-7. Contact the publisher, Jim Leisy, at Franklin, Beedle & Associates for further details.