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 Notes: [ PDF ] [ Video ]
- Supplement: Extended Transition Functions — Equivalence of Definitions: [ PDF ]
Lecture Presentation
Additional Information That May Be of Interest
- Lost in Space (Original Series)
- Lost in Space (Recent Remake)
- The Robot vs. the Aztec Mummy
- Devil Girl from Mars
- The Mysterians
- The Earth Dies Screaming
- Dr. Goldfoot and the Bikini Machine
- Santa Claus Conquers the Martians
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 Notes:: [ PDF ] [ Video ]
- Supplement: Correctness of a DFA — Proof of a Useful Result: [ PDF ]
Lecture Presentation
Additional Material That May Be of Interest
- Solar System
- Planets Beyond Neptune
- Pluto
- Eris
- IAU Definition of a Planet
- International Astronomical Union (IAU)
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
- Jonathan Archer
- Robert April
- Christopher Pike
- James T. KIrk
- Jean-Luc Picard
- Benjamin Sisko
- Kathryn Janeway
- Michael Burnham
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
- Doctor Who — First Doctor
- Doctor Who — Second Doctor
- Doctor Who — Third Doctor
- Doctor Who — Fourth Doctor
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 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
Assignment #1: Deterministic Finite Automata
Term Test #1: Finite Automata and Regular Languages
-
Information about the First Term Test
- Practice Test:
Test: [ LaTeX Source ] [ PDF ]
