Computer Science 313 — Finite Automata and Regular Expressions

Finte State Machine

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


University of Calgary Extension of Logo
Department of Computer Science

cpsc 313 computer science faculty of science u of c

cpsc 313 introduction to course finite automata and regular expressions assignments tests