This page introduces my book, Formal Language: A Practical Introduction (ISBN 9781590281970).

What is the book about?

The book is a undergraduate college-level introduction to formal languages, automata, computability, and complexity — topics at the foundations of computer science.

What makes this book different?

This book is written to be understood by all undergraduate students, regardless of their level of mathematical maturity.

If you ever teach this subject, ask yourself this question: 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.

So what about induction and other proof techniques?

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.

What kind of course is the book designed for?

The course for which I developed the book is called Introduction to the Theory of Computation. It was 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.

What exactly is covered in the book?

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

What supplementary materials are there?

A full set of PowerPoint lecture notes is available for each chapter, up through chapter 19. All the larger code examples from the text and exercises are there too. Sample solutions to the exercises are available through the publisher.

Will this book work for me?

I can only say for sure that it works for me. The first 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.

Where can I get the book?

The book is published by Franklin, Beedle & Associates (ISBN 9781590281970). You can go to the publisher’s Web site to order the book or to obtain a review copy. Or call them toll free in the USA; their phone number is 1-800-322-2665. Should you be calling from outside the USA, the number is 1-503-284-6348. The company’s address is:

Franklin, Beedle & Associates, Incorporated
2154 NE Broadway, Ste. 100
Portland, OR 97232
USA

 

Leave a reply

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> 

required