Finite Automata and Regular Languages
Overview
Initial lectures will concern simple abstract machines called deterministic finite automata and the languages that they recognize, which are called regular languages. Another kind of simple machine, called a nondeterministic finite automaton, will also be introduced. It will be proved that these also recognize the regular languages.
Regular expressions will also be introduced; these will be shown to recognize the same set of languages too. As will be briefly discussed, regular expressions have significant practical applications, so that these are supported in a variety of computing environments.
The study of deterministic finite automata and regular languages, in this course, includes an introduction to concepts, including design, verification, simulations (and proofs of equivalence of computational models) and impossibility results, that will be important later on in this course, and in at least one other course that computer science students will take later on. Your later studies will, ideally, be more straightforward if you understand and can work with these concepts now.
This material will be covered in lectures on September 5 – October 1 and in tutorials on September 11 – October 8.
Supplemental Material
You should not need any reference material, for this, that is not provided on the course web site. However, both of the following books include useful introductions to finite automata and regular languages.
- M. Sipser, Introduction to the Theory of Computation
Third Edition, CENGAGE Learning, 2013
- J. E. Hopcroft, R. Motwani, and J. D. Ullman,
Introduction to Automata Theory, Languages, and Computation
Third Edition, Pearson/Addison-Wesley, 2007
The first reference is a favourite of many people, partly because it is very well written (and easy to read). Unfortunately, it sometimes lacks details — just giving intuition when proofs might be expected, instead. The second is an update of a “classic” textbook in this area that is a bit more challenging to read, but includes the proofs that the first book sometimes omits.
Lecture #2: Introduction to Deterministic Finite Automata (Thursday, September 5)
Why This is Included
Once again, “you have to start somewhere”. In this lecture, the kind of abstract machine that we will initially be studying (“deterministic finite automata”) and the languages they define (“regular languages”) are introduced. Lecture activities are intended to help you to understand the definitions and notation being introduced — including how a given deterministic finite automaton processes an input string, and how a deterministic finite automaton defines (or “specifies”) a language. A technical result, relating two ways to define an “extended transition function”, is given because it will be needed later on, when proving properties of deterministic finite automata — and also to show how this kind of technical result can be proved, if you are interested in this.
Preparatory Reading
- Introduction to Deterministic Finite Automata: [ PDF ] [ Video ]
- Supplement: Extended Transition Functions — Equivalence of Definitions [ PDF ]
Lecture Presentation
Finishing Up
Tutorial #2: Introduction to Deterministic Finite Automata (Wednesday, September 11 and Thursday, September 12)
Lecture #3: DFA Design and Verification — Part One (Tuesday, September 10)
Why This is Included
One way, to prove that a given language L is a regular language, is to describe a deterministic finite automaton, and then prove that L is the language of this deterministic finite automaton. This lecture begins the introduction of a design process that you can use to do this.
A “longer term goal” here is to help you be become more familiar with “design processes” and comfortable using them: Considerably more complicated processes will be introduced later on.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #4: DFA Design and Verification — Part Two (Thursday, September 12)
Why This is Included
This lecture continues the presentation of a design process that can be used to design a deterministic finite automaton for a given language.
Once you designed a DFA you also need to confirm that your answer is correct. You might also need to convince somebody else of the correctness of your answer — and that other person might not be willing to take your word for it! This lecture material considers this too.
Preparatory Reading
- DFA Design and Verification — Part Two [ PDF ] [ Video ]
- Supplement: Completion of Example [ PDF ]
- Supplement: Completion of Another Example [ PDF ]
- Supplement: Proof of a Significant Technical Result [ PDF ]
Lecture Presentation
Finishing Up
Tutorial #3: DFA Design and Verification — Part One (Monday, September 16 and Tuesday, September 17)
Tutorial #4: DFA Design and Verification — Part Two (Wednesday, September 18 and Thursday, September 19)
Lecture #5: Introduction to Nondeterministic Finite Automata (Tuesday, September 17)
Why This is Included
Nondeterministic finite automata are abstract machines that differ from “deterministic finite automata” in one significant way: You may be allowed to go from a given state to zero, one, or even many states when you process a given symbol. Thus the processing of a symbol in a string (seemingly) involves guessing. This model is not very useful, by itself. However, understanding it will be helpful when another — more useful — way to specify languages is considered.
Lecture activities are intended to help you to understand the definitions and notation being introduced — including how a nondeterministic finite automaton processes an input string, and how a nondeterministic finitie automaton defines (or “specifies”) a language.
Preparatory Reading
- Introduction to Nondeterministic Finite Automata: [ PDF ] [ Video ]
- Supplement: Computation of λ-Closures [ PDF ]
Lecture Presentation
Finishing Up
Tutorial #5: Introduction to Nondeterministic Finite Automata (Monday, September 23 and Wednesday, September 24)
Lecture #6: Equivalence of Deterministic Finite Automata and Nondeterministic Finite Automata (Thursday, September 19)
Why This is Included
This lecture provides a constructive proof that “deterministic finite automata” and “nondeterministic finite automata” are equivalant in computational power. That is, a language L ⊆ Σ* is the language of a deterministic finite automaton if and only if it is the language of a nondeterministic finite automaton.
This result will be useful, in a future lecture, when another way to specify languages (using “regular expressions”) is considered. The proof technique — which includes the presentation and analysis of a simulation of one machine‘s computation with another“s — will useful again, when Turing machines are introduced.
Preparatory Reading
- Equivalence of DFAs and NFAs: [ PDF ] [ Video ]
- Supplement: Equivalence of Deterministic Finite Automata and Nondeterministic Finite Automata — Proofs of Claims [ PDF ]
- Supplement: A Bad Case for the Subset Construction [ PDF ]
Lecture Presentation
Finishing Up
Tutorial #6: Equivalence of Deterministic Finite Automata and Nondeterministic Finite Automata (Wednesday, September 25 and Thursday, September 26)
Lecture #7: Regular Operations and Regular Expressions (Tuesday, September 24)
Why This is Included
This lecture introduces (or, possibly, reviews) closure properties: You may have seen properties like these in a prerequisite course. These provide other ways to prove that a given language is a regular language. Furthermore, we will see, later, on, that they can sometimes be used to prove that a given language is not regular, as well. Understanding this will be useful, still later, because we will also see that similar “closure properties” can be used to prove that various problems cannot be solved using computers.
This lecture also provides another way to specify regular languages — using regular expressions. Understanding deterministic and nondeterministic finite automata can be helpful when you consider how the use of regular expressions in software is supported. As explained in supplemental (optional) material for the lecture, regular expressions are useful for performing searches and updates with text editors and word processors. They also have applications in database management and can be useful when searching the internet.
Preparatory Reading
- Regular Operations and Regular Expressions: [ PDF ] [ Video ]
- Supplement: Proofs of Closure Properties: [ PDF ]
- Supplement: Proof of Equivalence Claim: [ PDF ]
- Supplement: Parsing Regular Expressions: [ PDF ]
- Supplement: Regular Expressions in Practice: [ PDF ]
Lecture Presentation
Finishing Up
Tutorial #7: Regular Operations and Regular Expressions (Wednesday, October 2 and Thursday, October 3)
Lecture #8: Nonregular Languages, Part One (Thursday, September 26)
Why This is Included
This lecture provides a technical result that can — sometimes — be used to prove that a language is not regular. This result is used to identify several nonregular languages.
This complements the material in the lecture after this one — which provides other techniques, for proving that languages are not regular, that are somewhat more general and easier to use — but which cannot be used at all unless we already know about some nonregular languages.
Preparatory Reading
- Nonregular Languages, Part One: [ PDF ] [ Video ]
- Supplement: Proving That a Language is Not Regular —
Another Example
[ PDF ]
- Supplement: How to Use Quantifiers (Symbolic Logic Tutorial)
[ Video ]
Some of the notation, used in this video, might be different from what you have seen before — and it is not important that you understand the “syntax trees” that are described here — but this reviews a lot of the information about quantified variables that should have been introduced in a prerequisite for this course, and that students do not necessarily remember or fully understand. The “Pumping Lemma for Regular Languages” is sometimes misunderstood, or misused, because of this.
Lecture Presentation
Finishing Up
Lecture #9: Nonregular Languages, Part Two (Tuesday, October 1)
Why This is Included
Closure properties for regular languages were introduced in Lecture #7 — and it was shown, there, that they can be used to prove that languages are regular. As discussed in this lecture, they can also be used to prove that languages are not regular — provided that we already know about some nonregular languages. Thus this lecture depends on, and extends, the material in the lecture before it.
The idea that “closure properties” can be used to prove that certain problems are (in some sense) not easy to solve, with various computational devices, will appear again when Turing machines and computability are considered. Thus this lecture gives a reasonably simple application of an important idea that will used again (in a different setting) later on in the course.
