Computer Science 351 — Finite Automata and Regular Languages

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 equivalence of computational models) and impossibility results will be introduced — so that students can be more familiar with 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 May 5 – 19 and in tutorials on May 6 – 21. Students’ ability to solve problems using this material will be assessed using Assignment 1 and the midterm test.

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.

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 #1: Introduction to Deterministic Finite Automata (Tuesday, May 5)

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.

Please read the definitions concerning alphabets, strings and languages before completing required viewing for this lecture, if you have not already done so.

Preparatory Viewing and Reading

Lecture Presentation

Tutorial #1: Introduction to Deterministic Finite Automata (Wednesday, May 6 and Thursday, May 7)

This tutorial exercise concerns material from Lecture #1. Please read and try to solve the problems in this exercise before attending this tutorial where it is discussed.

Additional practice problems can be used to help prepare for assignmements and tests. Your solutions for these can be discussed with the instructor during his office hours.

Lecture #2: DFA Design and Verification (Thursday, May 7)

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 design and verification processes that you can use to do this.

A “longer term goal” is to help you to become more familiar with “design processes” and comfortable using them. Considerably more complicated design processes will be introduced later on.

Preparatory Viewing and Reading

Supplemental Material

Lecture Presentation

Tutorial #2: DFA Design and Verification (Monday, May 11 and Tuesday, May 12)

This tutorial exercise concerns material from Lecture #2. Please read and try to solve the problems in this exercise before attending the tutorial where it is discussed.

Lecture #3: Nondeterministic Finite Automata (Tuesday, May 12)

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.

After introducing nondeterministic finite automata, the preparatory material provides a constructive proof that “deterministic finite automata” and “nondeterministic finite automata” are equivalent 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.

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 finite automaton defines (or “specifies”) a language. They are also intended to use a given nondeterministic finite automaton to produce a deterministic finite automaton with the same language.

Preparatory Viewing and Reading

Supplemental Material

Lecture Presentation

Tutorial #3: Nondeterministic Finite Automata (Wednesday, May 13 and Thursday, May 14)

This tutorial exercise concerns material from Lecture #3. Please read and try to solve the problems in this exercise before attending the tutorial where it is discussed.

Lecture #4: Regular Operations and Regular Expressions (Thursday, May 14)

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 data analysis and can be useful when searching the internet.

Preparatory Viewing and Reading

Supplemental Material

Lecture Presentation

Tutorial #4: Regular Operations and Regular Expressions (Tuesday, May 19 and Wednesday, May 20)

This tutorial exercise concerns material from Lecture #4. Please read and try to solve the problems in this exercise before attending the tutorial where it is discussed.

Lecture #5: Nonregular Languages (Tuesday, May 19)

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.

Closure properties for regular languages were introduced in Lecture #4 — 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.

Preparatory Viewing and Reading

Supplemental Material

Lecture Presentation

Tutorial #5: Nonregular Languages (Thursday, May 21 and Monday, May 25)

This tutorial exercise concerns matrial from Lecture #5. Please read and try to solve the problems on this exercise before attending the tutorial where it is discussed.


University of Calgary Extension of Logo
Department of Computer Science

cpsc 351 computer science faculty of science u of c

cpsc 351 course outline intro and review finite automata and regular languages turing machines and computability discrete probability for computer science course admin assignments tests