Regular Languages and Finite Automata

Abstract

In this project for computer science students, we study the concept of finite automata and regular expressions as developed by Stephen Cole Kleene in his 1956 paper, “Representation of events in nerve nets and finite automata.” In particular, we learn Kleene’s own proof of the theorem, now called Kleene’s theorem, that shows finite automata and regular expressions are equivalent in their expressiveness for denoting languages. The project can be used in a senior undergraduate or beginning graduate level course on the theory of computation. Before working on the project, students are expected to have studied the concepts of finite automata and regular languages from a modern textbook.