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 1/23/2024. If you’re not already familiar with the book, you can read a pitch for it here.

Errata

Here is a a list of errors in the book, containing all those known to the author as of January 23, 2024.

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.)

Or you can download all pptx slides sets, zipped together

The slides can also be retrieved as pdf files:

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.

11 thoughts on “FL”

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..

Reply ↓

adam@webber-labs.com said on July 15, 2019 at 2:13 pm:

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

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.

Reply ↓

adam@webber-labs.com said on September 24, 2019 at 2:01 pm:

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

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.

Reply ↓

adam@webber-labs.com said on September 24, 2019 at 2:02 pm:

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

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

Reply ↓

adam@webber-labs.com said on September 30, 2019 at 6:13 pm:

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.
Reply ↓

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.

Reply ↓

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}*|?

Reply ↓

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

Reply ↓

student said on July 13, 2019 at 6:57 pm:

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..
Reply ↓
- adam@webber-labs.com said on July 15, 2019 at 2:13 pm:
  
  I’m so glad you find my Formal Languages helpful. Thanks for taking the time to tell me so!
  Reply ↓
Paul said on September 18, 2019 at 7:10 pm:

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.
Reply ↓
- adam@webber-labs.com said on September 24, 2019 at 2:01 pm:
  
  I’m glad that my book has helped you on your journey. Thanks for taking the time to tell me.
  Reply ↓
Mr X said on September 23, 2019 at 4:54 pm:

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.
Reply ↓
- adam@webber-labs.com said on September 24, 2019 at 2:02 pm:
  
  Thanks. I must admit, I’m a bit proud of it myself!
  Reply ↓
Paula Merns said on September 27, 2019 at 5:21 pm:

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
Reply ↓
- adam@webber-labs.com said on September 30, 2019 at 6:13 pm:
  
  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.
  Reply ↓
Denis Hudon said on December 8, 2019 at 3:18 am:

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.
Reply ↓
michael said on February 14, 2020 at 3:42 am:

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}*|?
Reply ↓
Rafael García said on June 25, 2022 at 2:21 am:

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
Reply ↓

Webber Labs

Computer Science from Adam Brooks Webber

FL

FORMAL LANGUAGE:
A Practical Introduction

Welcome

Errata

Lectures