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 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 — while studying abstract machines, and languages, that (unlike later ones) are not so complicated that details will be more confusing than necessary. Since regular expressions have numerous applications, as noted above, it concerns something that will help students to be more powerful users of various software tools and (potentially) better software developers.
Lecture #2: Introduction to Deterministic Finite Automata
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
Lecture #3: DFA Design and Verification
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 introduces a design process that you can use to do this.
Preparatory Reading
- DFA Design and Verification: [ PDF ] [ Video ]
- Supplement: Completion of Example [ PDF ]
- Supplement: Another Example [ PDF ]
- Supplement: Proof of a Significant Technical Result [ PDF ]
Lecture Presentation
Finishing Up
Tutorial #3: DFA Design and Verification
Lecture #4: Introduction to Nondeterministic Finite Automata
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 proceses 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 #4: Introduction to Nondeterministic Finite Automata
Lecture #5: Equivalence of Deterministic Finite Automata and Nondeterministic Finite Automata
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 — Proof of Claims [ PDF ]
Lecture Presentation
Finishing Up
Tutorial #5: Equivalence of Deterministic Finite Automata and Nondeterministic Finite Automata
Lecture #6: Regular Operations and Regular Expressions
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 manageemnt and can be useful when searching the internet.
Preparatory Reading
- Regular Operations and Expressions: [ PDF ] [ Video ]
- Supplement: Proofs of Closure Properties [ PDF ]
- Supplement: Proof of Equivalence Claim [ PDF ]
- Supplement: Appications of Regular Expressions [ PDF ]
Lecture Presentation
Finishing Up
Tutorial #6: Regular Operations and Regular Expressions
Lecture #7: Nonregular Languages, Part One
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
- Pumping Lemma for Regular Languages:
[ PDF ]
[ Video ]
- Supplement: Proving That a Language is Not Regular —
Another Example
[ PDF ]
-
How To Use Quantifiers (Symbolic Logic Tutorial):
Part of a sequence of tutorials introducing mathematical logic.
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
Tutorial #7: Nonregular Languages, Part One
Lecture #8: Nonregular Languages, Part Two
Why This is Included
Closure properties for regular languages were introduced in Lecture #6 — 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.
