Finite Automata

Finite Automata and Regular Languages

Overview

A course in theoretical computer science can be overwhelming because so many (seemingly) new things are being introduced at once. One way to deal with this is to keep some things simple (or familiar) so that other — new — things can be highlighted.

This course, therefore, continues with the introduction of an extremely simple model of computation — a finite state machine (also called a “finite automaton”). As this model is being studied, a variety of concepts, including design, verification, simulations (and proofs of equivalance of computational models) and impossibility results will be introduced — so that students can be more familiar will all of these. Ideally, this will make things less overwhelming later on, when a more complicated model of computation is introduced and studied (and all of these concepts are considered again).

Finite automata are also interesting as a model of computation (and not just as a teaching aid). A small amount of information, concerning applications of finite automata in text editing and word processing, other information processing, and compilation of programs, will also be given.

This material will be covered in lectures on September 4 – October 2 and in tutorials on September 7 – October 7. Students’ ability to solve problems using this material will be assessed using Assignment 1 and Term Test 1.

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

Why This is Included

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 the language of a deterministic finite automaton is defined. A little bit of information, about how you can prove that a given language is the language of a given deterministic finite automaton, will also be given. This is all needed for the material that will follow.

Preparatory Viewing and Reading

Lecture Presentation

Tutorial #2: Introduction to Deterministic Finite Automata (Wednesday, September 10 and Thursday, September 11)

Lecture #3: DFA Design and Verification — Part One (Tuesday, September 9)

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 to become more familiar with “design processes” and comfortable using them: Considerably more complicated processes will be introduced later on.

Preparatory Viewing and Reading

Lecture Presentation

Lecture #4: DFA Design and Verification — Part Two (Thursday, September 11)

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 and Viewing

Lecture Presentation

Tutorial #3: DFA Design and Verification — Part One (Monday, September 15 and Tuesday, September 16)

Lecture #5: Introduction to Nondeterministic Finite Automata (Tuesday, September 16)

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 and Viewing

Lecture #6: Equivalence of Deterministic Finite Automata and Nondeterministic Finite Automata (Thursday, September 18)

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 and Viewing

Lecture #7: Regular Operations and Regular Expressions (Tuesday, September 23)

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 and Viewing

Regular Operations and Regular Expressions [ Video: 22:54 ]

Lecture #8: Nonregular Languages, Part One (Thursday, September 26)

Why This is Included

Impossibility results, that is, claims and proofs that problems cannot be solved, are (almost certainly) the most important “new thing” in this course. One of the simplest kinds of these are claims and proofs that languages are not regular.

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 and Viewing

Lecture #9: Nonregular Languages, Part Two (Tuesday, October 2)

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.