# FORMAL LANGUAGE:

A Practical Introduction

Dr. Adam Brooks Webber

## Welcome

This page accesses supporting material for the book *Formal Language: A Practical Introduction* (ISBN 1-590281-97-7) by Adam Webber. This page was last updated on 9/30/2019. If you’re not already familiar with the book, you can read a pitch for it here.

## Errata

Here is a list of errors in the book, containing all those known to the author as of September 30, 2019.

## Lectures

These are PowerPoint slide sets for lectures, one for each chapter of the book through chapter 19. (When I have taught the course, I have always stopped at the end of chapter 18. I have also lectured from chapter 19 in a separate course. But although I have used chapters 20 and 21, and the appendices, in independent studies courses, I have never organized lecture notes for them. If you do, and if you email them to me, I’ll post them here.)

- Introduction and Chapter 1: Fundamentals
- Chapter 2: Finite Automata
- Chapter 3: Closure Properties for Regular Languages
- Chapter 4: DFA Applications
- Chapter 5: Nondeterministic Finite Automata
- Chapter 6: NFA Applications
- Chapter 7: Regular Expressions
- Chapter 8: Regular Expression Applications
- Chapter 9: Advanced Topics in Regular Languages
- Chapter 10: Grammars
- Chapter 11: Non-Regular Languages
- Chapter 12: Context-Free Languages
- Chapter 13: Stack Machines
- Chapter 14: The Context-Free Frontier
- Chapter 15: Stack Machine Applications
- Chapter 16: Turing Machines
- Chapter 17: Computability
- Chapter 18: Uncomputability
- Chapter 19: Cost Models

Or you can download all 19 pptx slide sets, zipped together.

The slides can also be retrieved as pdf files:

- Introduction and Chapter 1: Fundamentals
- Chapter 2: Finite Automata
- Chapter 3: Closure Properties for Regular Languages
- Chapter 4: DFA Applications
- Chapter 5: Nondeterministic Finite Automata
- Chapter 6: NFA Applications
- Chapter 7: Regular Expressions
- Chapter 8: Regular Expression Applications
- Chapter 9: Advanced Topics in Regular Languages
- Chapter 10: Grammars
- Chapter 11: Non-Regular Languages
- Chapter 12: Context-Free Languages
- Chapter 13: Stack Machines
- Chapter 14: The Context-Free Frontier
- Chapter 15: Stack Machine Applications
- Chapter 16: Turing Machines
- Chapter 17: Computability
- Chapter 18: Uncomputability
- Chapter 19: Cost Models

Or you can download all 19 pdf slide sets, zipped together.

## Source Code

Here are the sources for the longer Java examples from the book.

### Chapter 4

- The Mod3 example: Mod3.java and Mod3Filter.java

### Chapter 6

- An NFA implementation with backtracking search: NFA1.java and NFA1Filter.java
- An NFA implementation with bit-mapped parallel search: NFA2.java and NFA2Filter.java

### Chapter 8

- A regular expression example in Java: RegexFilter.java

## Contacts

You can email me here with comments and questions about the book.

Instructors can request sample solutions to all the exercises in the book; contact Tom Sumner at Franklin Beedle (tsumner@fbeedle.com) for access to that material.

i wish i had a math teacher like you for my CS-engineering course study period, who could have explained this subject in such a crystal clear manner with strong emphasize on foundation topics…The math teacher who instead came to teach us, behaved like talking was a sin, and even when he uttered one or two words he said it in such low voice that nobody could hear it.. then our teacher would silently write some symbols in blackboard and will waste time and go..someof us asked doubts hoping we could clarify matters, but the more questions we asked the lesser our professor talked.. He was supposed to be a math genius having PhD and stuff… I failed in the exam the first time.. and i always considered Formal languages as a tough subject.. but when i read your book, i was astonished to see ho clearly and in what simple manner you have explained it all.. wonderful work sir.. students who got you as teacher on this subjects are really lucky..

I’m so glad you find my Formal Languages helpful. Thanks for taking the time to tell me so!

I have been using your book for self study and find it much easier to follow than what was assigned at my school. Thank you for writing such a great book.

I’m glad that my book has helped you on your journey. Thanks for taking the time to tell me.

Good book.. Although not very well-known, sadly.. I found it by chance.. Very nice to run alongside Sethi, Aho and other such material.. Thank you.

Thanks. I must admit, I’m a bit proud of it myself!

I have been enjoying teaching from this book and my students have found the material far more accessible than the Sipser title it replaced. Even the network focused students are enjoying being able to see the machines work in code.

We noted that the subscript in chapter 3, exercise 4, letter b on the Bar L in the first part of the intersection is cut off and cannot be seen. Is this subscript supposed to be a 1?

Thank you,

Paula Merns

Thank you, Paula. I’m glad you’re find the book useful. Thanks for taking the time to tell me so

Yes, the subscript there should be a 1. I’ve updated the errata to reflect this.

First off, I really like this textbook. It’s well-organized, readable, and, for me at least, makes just the right number of assumptions about my understanding. I’ve suffered through some really bad text books over the years and this is an oasis in the desert.

I think I’ve found an error not listed in the link above. On page 192, for Lemma 14.2.3, should line 4 read:

4. for all i, uv^iwx^iy ∈ L

I couldn’t find a unicode character for a superscript i so I threw some carats in there.

I believe on exercise 4 in section 3, the a loop should be removed for L3.

Otherwise, would L3 not be {x,a,y,b,z | x,y,z in {x,y}*|?

Excellent material. I had found it a long time ago, and I will use it in my next course that I will teach to my students at the Faculty of Engineering of the University of Guerrero in Mexico. I also read about your spiritual work, I have already subscribed to your page