#
Finite Automata and Regular Expressions

##
Overview

Initial lectures will concern simple abstract machines called
*deterministic finite automata* and the languages
that they recognize. Another kind of simple machine called a
*nondeterministic finite automaton* will be introduced
and proved to recognize the same set of languages. *Regular
expressions* will also be introduced and will be shown to
recognize the same set of languages too. As briefly discussed, regular
expressions have significant practical applications, so that these are
supported in a variety of computing environments.

During this study, students will be introduced to a simple *design
process* that can be used to design deterministic finite automata
with given languages, and to show that their answers are correct. Students will also
see various proofs of various properties of simple machines as well as processes
that can be used to convert one kind of simple machine (or expression) to another.

##
Lecture #2: Introduction to Deterministic Finite Automata

###
Required Reading

###
Lecture Presentation

###
Additional Information That May Be of Interest

##
Lecture #3: Designing a Deterministic Finite Automaton

###
Required Reading

###
Lecture Presentation

###
Additional Material That May Be of Interest

##
Tutorial Exercise #2: Interpretation and Design of Deterministic
Finite Automata

##
Lecture #4: Verification of a Deterministic Finite Automaton

###
Required Reading

###
Lecture Presentation

###
Additional Material That May Be of Interest

##
Tutorial Exercise #3: Design and Verification of Deterministic Finite Automata

##
Lecture #5: Introduction to Nondeterministic Finite Automata

###
Required Reading

###
Lecture Presentation

###
Additional Material That May Be of Interest

##
Tutorial Exercise #4: Nondeterministic Finite Automata

##
Lecture #6: Equivalence of DFAs and NFAs

###
Required Reading

###
Lecture Presentation

###
Additional Information That May Be of Interest

##
Tutorial Exercise #5: Equivalence of Deterministic Finite Automata
and Nondeterministic Finite Automata

##
Lecture #7: Regular Operations

###
Required Reading

###
Lecture Presentation

###
Additional Information That May Be of Interest

##
Tutorial Exercise #6: Closure Properties of Regular Languages

##
Lecture #8: Regular Expressions (Part One)

###
Required Reading

###
Lecture Presentation

###
Additional Information That May Be of Interest

##
Lecture #9: Regular Expressions (Part Two)

###
Required Reading

- Lecture Notes:
[ PDF ]
- Supplement: Applications of Regular Expressions:
[ PDF ]

###
Lecture Presentation

###
Additional Material That May Be of Interest

##
Tutorial Exercise #7: Regular Expressions

##
Lecture #10: Nonregular Languages, Part One

###
Required Reading

###
Lecture Presentation

##
Lecture #11: Nonregular Languages, Part Two

###
Required Reading

###
Lecture Presentation

##
Tutorial Exercise #8: Nonregular Languages