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